EasyArraysAI interview only
Missing Number
Asked atamazonmicrosoftapplemetagooglebloomberg
01 · Problem
You are given an array nums holding n distinct integers, all taken from the range [0, n]. Since the range contains n + 1 values and the array has only n, exactly one value from the range is absent.
Return the missing value. Try to use O(1) extra space and O(n) time.
02 · Examples
Example 01
Input
nums = [3,0,1]
Output
2
n = 3, so the range is [0, 3]. The values 0, 1 and 3 are present, so 2 is missing.
Example 02
Input
nums = [0,1]
Output
2
n = 2, so the range is [0, 2]. Both 0 and 1 are present, so the missing value is 2.
Example 03
Input
nums = [9,6,4,2,3,5,7,0,1]
Output
8
n = 9, so the range is [0, 9]. Every value except 8 appears.
03 · Constraints
- 01n == nums.length
- 021 <= n <= 104
- 030 <= nums[i] <= n
- 04All values in nums are distinct
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.