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

Hiring now

Nvidia has 1,936 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior System Software Engineer
India, Pune
Senior E2E Hardware Architect, AI Networking
Israel, Yokneam
Senior Software Engineer - Infrastructure
India, Pune

Or practice this question first

Next question