InternDoor

The number that is not there

Easyarrays · math · bit manipulation

Reported in interviews at (where)

nums holds n different whole numbers, all taken from 0 to n (that range has n + 1 numbers), in any order. Exactly one number from the range is missing.

Return it. Can you do it with no extra list, in one pass?

Example 1
Input
nums = [4,2,0,1]
Output
3

n = 4, so the range is 0 to 4, and 3 is the one not in the list.

Example 2
Input
nums = [1]
Output
0

n = 1: the range is 0 and 1.

Limits

  • 1 <= n == nums.length <= 100000
  • 0 <= nums[i] <= n
  • All values in nums are different.

Hints

Hint 1

The numbers 0 to n add up to n(n + 1) / 2.

Hint 2

Or XOR every index and every value together: pairs cancel.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.