[LeetCode] 268. Missing Number

https://leetcode.com/problems/missing-number/description/

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Missing Number

문제 유형 : 정렬, 해시, 비트마스킹, 수학

문제 난이도 : Easy

 

문제

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

[0, n]에서 n개의 정수를 담은 배열 nums가 주어진다.

이 중 하나가 빠져있는데, 그 수를 찾아내시오.

 

풀이

해싱과 정렬을 이용한 풀이는 너무 쉬우므로 생략하겠다.

해싱은 O(n)의 시간복잡도와 공간복잡도,

정렬은 O(nlogn)의 시간복잡도와 O(1)의 공간복잡도이다.

 

수학적인 풀이와 비트마스킹을 이용한 풀이는 O(n)의 시간복잡도와 O(1)의 공간복잡도를 가진다.

 

1. 수학적인 풀이

수의 전체 합을 구한다. n(n+1)/2를 하여 구한다.

배열을 순차적으로 순회하면서 합에서 하나하나 뺀다.

최종적으로는 없었던 수가 남는다.

 

2. 비트마스킹

모든 수는 자기 자신과 XOR연산을 할 경우, 0이 된다.

그러므로 각 수와 각 인덱스를 XOR한 값에 연달아 XOR 연산을 하면, 있는 수들은 0으로 상쇄되고, 최종적으로 없는 수만 남는다.

변수에 0을 담아서 순차적으로 위 연산을 하면, 최종적으로 없었던 수가 남는다.

 

코드

C++ - 수학적인 접근

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int n = nums.size();
        int sum = n*(n+1)/2;

        for(const auto &num : nums) {
            sum -= num;
        }

        return sum;
    }
};

Go - 비트마스킹

func missingNumber(nums []int) int {
    missing := 0

    for i, v := range nums {
        missing ^= (i+1) ^ v
    }

    return missing
}