Home | Projects | Notes > Problem Solving > LC - E - 268. Missing Number (bit manipulation)

LC - E - 268. Missing Number (bit manipulation)

Solutions in C++

Solution 1

This solution uses bit manipulation. XOR operations has the following properties:

XORing a number by itself results in 0.
XOR is commutative and associative.

Complexity Analysis:

$T = O(n)$ $n$ is the number of elements of the given vector
$S = O(1)$

Solution:


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    int missingNumber(vector<int>& nums) {
4
        int ret = nums.size()
5
        int i = 0;
6

7
        for (auto n : nums)
8
        {
9
            ret ^= n;
10
            ret ^= i;
11
            ++i;
12
        }
13

14
        return ret;
15
    }
16
};

Solution 2

$sum_{i = 0}^{n}(n) = n(n+1)/2$ .

Complexity Analysis:

$T = O(n)$ $n$ is the number of elements of the given vector
$S = O(1)$

Solution:


xxxxxxxxxx
12
1
class Solution {
2
public:
3
    int missingNumber(vector<int>& nums) {
4
        int n = nums.size();
5
        int ret = n * (n + 1) / 2;
6

7
        for (auto n : nums)
8
            ret -= n;       
9

10
        return ret;
11
    }
12
};

Solution 3

This solution uses the std::sort algorithm.

Complexity Analysis:

$T = O(n\log n)$ $n$ is the number of elements of the given vector
$S = O(1)$

Solution:


xxxxxxxxxx
15
1
class Solution {
2
public:
3
    int missingNumber(vector<int>& nums) {
4
        std::sort(nums.begin(), nums.end());
5
        int n = nums.size();
6

7
        for (int i = 0; i < nums.size(); ++i)
8
        {
9
            if (nums[i] != i)
10
                return i;
11
        }
12

13
        return n;
14
    }
15
};

Solutions in C

Solution 1

This solution uses bit manipulation. XOR operations has the following properties:

XORing a number by itself results in 0.
XOR is commutative and associative.

Complexity Analysis:

$T = O(n)$ $n$ is the number of elements of the given array
$S = O(1)$

Solution:


xxxxxxxxxx
12
1
int missingNumber(int* nums, int numsSize){
2
    int ret = numsSize;
3
    int i;
4

5
    for (i = 0; i < numsSize; ++i)
6
    {
7
        ret ^= nums[i];
8
        ret ^= i;
9
    }
10

11
    return ret;
12
}