[알고리즘] LeetCode 268번 "Missing Number" (C/C++) - Don 임베디드

문제요약:

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.

 

 

제약:

n = nums.size()

1 <= n <= 10^4

0 <= nums[i] <= n

all the numbers in nums are nuique.

 

예제 1 입력.	예제 1 출력.
nums = [3,0,1]	2
예제 2 입력.	예제 2 출력.
nums = [0,1]	2
예제 3 입력.	예제 3 출력.
nums = [9,6,4,2,3,5,7,0,1]	8

 

 

정답코드 1:

O(n) average case, O(n^2) worst case

class Solution {
public:
    unordered_set <int> myHashset;
    
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++)
        {
            myHashset.insert(nums[i]);
        }
        for (int j = 0; j <= nums.size(); j++)
        {
            if(myHashset.find(j) == myHashset.end())
            {
                return j;
            }
        }
        // input error.
        return INT_MAX;
    }
};

핵심 Idea:

  Store elements in nums in a hashmap.

  Search every elements until there's no element found.

---

정답코드 2:

O(n) worst case.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int nMissing = 0;
        nMissing ^= n;
        
        for (int i = 0 ; i < n; i++)
        {
            nMissing ^= (i^nums[i]);
        }
        return nMissing;
    }
};

핵심 Idea:

XOR bit manipulation
(a ^ x ^ x) == (x ^ a ^ x) == (x ^ x ^ a) == a

if we have a number a = 0,

and XOR numbers from 0 to n twice,

int main()
{
    int a = 0;
    for(int i = 0; i <= n; i++)
    {
        a ^= i; // XOR step1
        a ^= i; // XOR step2
    }
    return a;
}

the returned value would be 0.

 

Among all the elements from 0 to n,

if we change the algorithm to do XOR operation only once on element k,

the returned value would be k.

 

 

원본 링크: https://leetcode.com/problems/missing-number/solution/