Problem

Given an array of size n-2 containing unique numbers from 1 to n (inclusive) with exactly two numbers missing, find the two missing numbers.

Examples

Example 1

1
2

Input: nums = [2, 1, 5, 8, 6, 7, 3, 9], n = 10
Output: [4, 10]  // (order does not matter)

Solution

Method 1 – Math (Sum and Product, with caveats)

Let the missing numbers be p and q.

  • The sum of numbers from 1 to n: S = n*(n+1)/2
  • The sum of the array: S1 = sum(nums)
  • So, p + q = S - S1
  • The product of numbers from 1 to n: P = n!
  • The product of the array: P1 = product(nums)
  • So, p * q = P / P1

Solve the quadratic equation: x^2 - (p+q)x + (p*q) = 0

Note: This approach is not recommended for large n due to overflow in product calculation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <cmath>
class Solution {
public:
    std::vector<int> findMissingTwo(const std::vector<int>& nums, int n) {
        long long S = (long long)n * (n + 1) / 2;
        long long S1 = 0, P1 = 1, P = 1;
        for (int x : nums) {
            S1 += x;
            P1 *= x;
        }
        for (int i = 1; i <= n; ++i) P *= i;
        long long s = S - S1;
        long long p = P / P1;
        long long d = (long long)std::sqrt(s * s - 4 * p);
        int x = (int)((s + d) / 2);
        int y = (int)(s - x);
        return {x, y};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import "math"
func findMissingTwo(nums []int, n int) []int {
    S := n * (n + 1) / 2
    S1, P1, P := 0, 1, 1
    for _, x := range nums {
        S1 += x
        P1 *= x
    }
    for i := 1; i <= n; i++ {
        P *= i
    }
    s := S - S1
    p := P / P1
    d := int(math.Sqrt(float64(s*s - 4*p)))
    x := (s + d) / 2
    y := s - x
    return []int{x, y}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[] findMissingTwo(int[] nums, int n) {
        long S = (long)n * (n + 1) / 2;
        long S1 = 0, P1 = 1, P = 1;
        for (int x : nums) {
            S1 += x;
            P1 *= x;
        }
        for (int i = 1; i <= n; i++) P *= i;
        long s = S - S1;
        long p = P / P1;
        long d = (long)Math.sqrt(s * s - 4 * p);
        int x = (int)((s + d) / 2);
        int y = (int)(s - x);
        return new int[]{x, y};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import math
class Solution:
    def findMissingTwo(self, nums: list[int], n: int) -> list[int]:
        S = n * (n + 1) // 2
        S1 = sum(nums)
        P = math.prod(range(1, n+1))
        P1 = 1
        for x in nums:
            P1 *= x
        s = S - S1
        p = P // P1
        # x^2 - s*x + p = 0
        d = int((s**2 - 4*p)**0.5)
        x = (s + d) // 2
        y = s - x
        return [x, y]

Complexity

  • ⏰ Time: O(n)
  • 🧺 Space: O(1) (but beware of overflow)

Method 2 – In-place Marking (Negation, O(n) time, O(1) space, but mutates input)

This approach avoids multiplication and uses the fact that the numbers are positive and in the range [1, n].

We use each element of the array nums as an index to mark presence. For each value nums[i], we mark the element at index abs(nums[i]) - 1 as negative. After marking, the indices that remain positive correspond to the missing numbers.

A subtlety: If we simply overwrite values (e.g., setting to 0), we lose information. By negating the value at the index, we preserve the original value (up to sign) and can later restore the array if needed. For example, if nums = [2, 1, 5, 8, 6, 7, 3, 9], after marking, the positive entries indicate the missing numbers.

After marking, a second pass over nums finds all indices with positive values—these are the missing numbers (add 1 to the index to get the actual number). Optionally, you can restore the array by negating all negative values back to positive.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <vector>
#include <cmath>
class Solution {
public:
    std::vector<int> findMissingTwo(std::vector<int> nums, int n) {
        for (int x : nums) {
            int idx = std::abs(x) - 1;
            if (idx < n) nums[idx] = -std::abs(nums[idx]);
        }
        std::vector<int> res;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) res.push_back(i + 1);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func findMissingTwo(nums []int, n int) []int {
    arr := make([]int, len(nums))
    copy(arr, nums)
    for _, x := range arr {
        idx := abs(x) - 1
        if idx < n {
            arr[idx] = -abs(arr[idx])
        }
    }
    res := []int{}
    for i := 0; i < n; i++ {
        if arr[i] > 0 {
            res = append(res, i+1)
        }
    }
    return res
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int[] findMissingTwo(int[] nums, int n) {
        int[] arr = nums.clone();
        for (int x : arr) {
            int idx = Math.abs(x) - 1;
            if (idx < n) arr[idx] = -Math.abs(arr[idx]);
        }
        int[] res = new int[2];
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > 0) res[j++] = i + 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def findMissingTwo(self, nums: list[int], n: int) -> list[int]:
        arr = nums[:]
        for x in arr:
            idx = abs(x) - 1
            if idx < n:
                arr[idx] = -abs(arr[idx])
        return [i+1 for i in range(n) if arr[i] > 0]

Complexity

  • ⏰ Time: O(n)
  • 🧺 Space: O(1) (if mutation allowed)

Method 3 – XOR Partitioning (O(n) time, O(1) space, immutable input)

The above solution assumes that the input array is mutable. But what if nums is immutable and we still need to find the missing values in O(n) time and constant space? Here, we use the properties of XOR.

If there were no missing numbers, then the XOR of all numbers from 1 to n (let’s call it xor1 = 1 ^ 2 ^ ... ^ n) and the XOR of all numbers in the array (xor2 = nums[0] ^ nums[1] ^ ... ^ nums[n-3]) would be equal, so their XOR would be 0.

With two missing numbers, the XOR of all numbers from 1 to n and all elements in nums gives xor = p ^ q, where p and q are the missing numbers. All bits set in xor are set in either p or q.

To separate p and q, pick any set bit in xor (commonly the rightmost set bit, which can be found as mask = xor & -xor). Partition all numbers from 1 to n and all elements in nums into two groups based on this bit, and XOR within each group. This will isolate p in one group and q in the other.

This approach works in O(n) time and O(1) space, and does not modify the input array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def findMissingTwo(self, nums: list[int], n: int) -> list[int]:
        xor = 0
        for x in nums:
            xor ^= x
        for i in range(1, n+1):
            xor ^= i
        # Find rightmost set bit
        mask = xor & -xor
        a = b = 0
        for x in nums:
            if x & mask:
                a ^= x
            else:
                b ^= x
        for i in range(1, n+1):
            if i & mask:
                a ^= i
            else:
                b ^= i
        return [a, b]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int[] findMissingTwo(int[] nums, int n) {
        int xor = 0;
        for (int x : nums) xor ^= x;
        for (int i = 1; i <= n; i++) xor ^= i;
        int mask = xor & -xor;
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x & mask) != 0) a ^= x;
            else b ^= x;
        }
        for (int i = 1; i <= n; i++) {
            if ((i & mask) != 0) a ^= i;
            else b ^= i;
        }
        return new int[]{a, b};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
class Solution {
public:
    std::vector<int> findMissingTwo(const std::vector<int>& nums, int n) {
        int xorv = 0;
        for (int x : nums) xorv ^= x;
        for (int i = 1; i <= n; ++i) xorv ^= i;
        int mask = xorv & -xorv;
        int a = 0, b = 0;
        for (int x : nums) {
            if (x & mask) a ^= x;
            else b ^= x;
        }
        for (int i = 1; i <= n; ++i) {
            if (i & mask) a ^= i;
            else b ^= i;
        }
        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

func findMissingTwo(nums []int, n int) []int {
    xor := 0
    for _, x := range nums {
        xor ^= x
    }
    for i := 1; i <= n; i++ {
        xor ^= i
    }
    mask := xor & -xor
    a, b := 0, 0
    for _, x := range nums {
        if x&mask != 0 {
            a ^= x
        } else {
            b ^= x
        }
    }
    for i := 1; i <= n; i++ {
        if i&mask != 0 {
            a ^= i
        } else {
            b ^= i
        }
    }
    return []int{a, b}
}

Complexity

  • ⏰ Time: O(n)
  • 🧺 Space: O(1)