(Binary, Easy) Missing Number

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

O(n) 시간복잡도로 풀라는데, 사실 Binary라고 고정하지 않고 생각하면 쉽다.

그냥 n+1 사이즈로 카피 배열을 만들어서 nums[i]값을 인덱스로 값을 세팅해주면 된다.. boolean이든, 아니면 범위에서 벗어난 int값(예를 들어 -1)을 활용하든.

한번 순회하면 빵꾸난 부분에서 false 또는 -1등 플래그로 찾을 수 있으므로 이것을 만나면 리턴하면 된다. for문 두 번이므로 O(n)은 맞다.

class Solution {
    public int missingNumber(int[] nums) {
        int n =  nums.length;

        boolean[] hits = new boolean[n+1];
        for (int i=0; i<n; i++) {
            hits[nums[i]] = true;
        }

        for (int i=0; i<hits.length; i++) {
            if (!hits[i]) return i;
        }
        return 0;
    }
}

아니면 수학적으로 0부터 n까지의 합은 n * (n + 1) / 2 이므로 간단하게 총합을 계산한 뒤에 O(n)으로 실제 nums의 총합을 계산하고 차액이 답인 것으로 할 수도 있다.

class Solution {
    public int missingNumber(int[] nums) {
        int n =  nums.length;

        int sum = n * (n + 1) / 2;
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        
        return sum - actual;
    }
}

근데 태그가 Bit Manipulation이고 75제 제공 링크에서도 Binary로 분류하고 있으니 다른 방법이 있지 않을까 고민을 해봤다.

AND연산을 어떻게 잘 해보면 되지 않을까 고민하다가 잘 안떠올라서 이것도 솔루션 참고 - XOR 결과로 누락건을 찾을 수 있다.

동일한 수로 XOR 한 경우 결과는 0이다.
0에다 어떤 수를 XOR 연산하면 그 수가 그대로 리턴된다.

0^0 = 0
1^1 = 0
3^3 = 0
0^0^2^0 = 2

따라서 0부터 n까지 XOR 연산한 결과를 특정 변수에 담아두고,
다시 nums를 순회하며 nums[i] 값으로 XOR 연산을 수행하면 구멍난 부분을 찾을 수 있다.

class Solution {
    public int missingNumber(int[] nums) {
        int n =  nums.length;

        int result = 0;
        for (int i=0; i<=n; i++) {
            result = result ^ i;
        }

        for (int i=0; i<n; i++) {
            result = result ^ nums[i];
        }

        return result;
    }
}