LeetCode - Algorithms - 268. Missing Number

Problem

268. Missing Number

Java

leetcode solution

© Approach 3 Bit Manipulation

1
2
3
4
5
6
7
8
9
class Solution {
    public int missingNumber(int[] nums) {
        final int N = nums.length;
        int r = N;
        for (int i = 0; i < N; i++)
            r ^= i ^ nums[i];
        return r;        
    }
}

Submission Detail

  • 122 / 122 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Missing Number.
  • Memory Usage: 47.8 MB, less than 5.40% of Java online submissions for Missing Number.

2

© Bitwise operators — Facts and Hacks - Compute XOR from 1 to n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int missingNumber(int[] nums) {
        final int N = nums.length;
        int x = computeXOR(N);
        x = 0 ^ x;
        int y = nums[0];
        for (int i = 1; i < N; i++) {
            y = y ^ nums[i];
        }
        return x ^ y;        
    }
    
    private int computeXOR(int n) {
        if (n % 4 == 0) return n;
        if (n % 4 == 1) return 1;
        if (n % 4 == 2) return n + 1;
        else return 0;
    }
}

Submission Detail

  • 122 / 122 test cases passed.
  • Runtime: 1 ms, faster than 40.83% of Java online submissions for Missing Number.
  • Memory Usage: 48 MB, less than 5.40% of Java online submissions for Missing Number.