Skip to content

17.19. Missing Two

Description

You are given an array with all the numbers from 1 to N appearing exactly once, except for two number that is missing. How can you find the missing number in O(N) time and 0(1) space?

You can return the missing numbers in any order.

Example 1:

Input: [1]

Output: [2,3]

Example 2:

Input: [2,3]

Output: [1,4]

Note:

  • nums.length <= 30000

Solutions

Solution 1

Thinking

Two numbers are missing from \(1\ldots n\). Sum and sum-of-squares work but squares overflow easily.

XOR of everything is \(a\oplus b\). lowbit splits them into different groups (that bit is \(1\) in one and \(0\) in the other); XOR inside a group isolates each.

Compute \(xor\), then XOR values with \(diff=xor\&(-xor)\) set to get \(a\), and \(b=xor\oplus a\). Linear time, constant space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums) + 2
        xor = 0
        for v in nums:
            xor ^= v
        for i in range(1, n + 1):
            xor ^= i

        diff = xor & (-xor)
        a = 0
        for v in nums:
            if v & diff:
                a ^= v
        for i in range(1, n + 1):
            if i & diff:
                a ^= i
        b = xor ^ a
        return [a, b]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;
        int xor = 0;
        for (int v : nums) {
            xor ^= v;
        }
        for (int i = 1; i <= n; ++i) {
            xor ^= i;
        }
        int diff = xor & (-xor);
        int a = 0;
        for (int v : nums) {
            if ((v & diff) != 0) {
                a ^= v;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if ((i & diff) != 0) {
                a ^= i;
            }
        }
        int b = xor ^ a;
        return new int[] {a, b};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int eor = 0;
        for (int v : nums) eor ^= v;
        for (int i = 1; i <= n; ++i) eor ^= i;

        int diff = eor & -eor;
        int a = 0;
        for (int v : nums)
            if (v & diff) a ^= v;
        for (int i = 1; i <= n; ++i)
            if (i & diff) a ^= i;
        int b = eor ^ a;
        return {a, b};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func missingTwo(nums []int) []int {
    n := len(nums) + 2
    xor := 0
    for _, v := range nums {
        xor ^= v
    }
    for i := 1; i <= n; i++ {
        xor ^= i
    }
    diff := xor & -xor
    a := 0
    for _, v := range nums {
        if (v & diff) != 0 {
            a ^= v
        }
    }
    for i := 1; i <= n; i++ {
        if (i & diff) != 0 {
            a ^= i
        }
    }
    b := xor ^ a
    return []int{a, b}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    func missingTwo(_ nums: [Int]) -> [Int] {
        let n = nums.count + 2
        var xor = 0

        for num in nums {
            xor ^= num
        }

        for i in 1...n {
            xor ^= i
        }

        let diff = xor & (-xor)

        var a = 0

        for num in nums {
            if (num & diff) != 0 {
                a ^= num
            }
        }

        for i in 1...n {
            if (i & diff) != 0 {
                a ^= i
            }
        }

        let b = xor ^ a
        return [a, b]
    }
}

Comments