Coding

Find missing number

Asked at

Nvidia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array of size n containing distinct values in the range from 0 to n (inclusive), return the only number missing from the array within this range.

Input: nums = [0, 2, 3, 1, 4] Output: 5 Explanation: nums contains 0, 1, 2, 3, 4 thus leaving 5 as the only missing number in the range [0, 5]

Input: nums = [0, 1, 2, 4, 5, 6] Output: 3 Explanation: nums contains 0, 1, 2, 4, 5, 6 thus leaving 3 as the only missing number in the range [0, 6]

Input: nums = [1, 3, 6, 4, 2, 5]

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.

cpp

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        
    }
};

java

class Solution {
    public int missingNumber(int[] nums) {
        
    }
}

python

class Solution:
    def missingNumber(self, nums):

javascript

class Solution {
    missingNumber(nums) {

    }
}

csharp

public class Solution {
    public int MissingNumber(List<int> nums) {

    }
}

func missingNumber(nums []int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Use the fact that expected values are 0 through n.
02Either sum the expected range and subtract array values or XOR both sets.
03Prefer XOR when overflow is a concern.
04Return the remaining unmatched value.

Reference answer

XOR is a clean O(n)-time, O(1)-space solution. Initialize missing=n, then for each index i and value x, XOR missing ^= i ^ x. The indices contribute 0..n-1, and the initial n completes the expected range 0..n; equal values cancel because a ^ a = 0, leaving the missing one. Alternatively calculate n(n+1)/2 - sum(nums) with a wide integer. Sorting or a set is unnecessary. This relies on the promise that values are distinct and all lie in the stated range; with duplicates or out-of-range values, neither invariant identifies a unique answer. The XOR approach avoids summation overflow and is order-independent, so it is usually the strongest interview answer for this exact contract.

Then expect these follow-ups

How would you find a duplicate when values are 1..n?
Tests: cycle detection or arithmetic
How would you handle many missing values?
Tests: set/bitset trade-offs

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question