Skip to content

Missing Number

Sar Champagne Bielert edited this page Apr 8, 2024 · 6 revisions

Unit 1 Session 2 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Will the array ever contain duplicate numbers?
    • No. Each number in the array will be distinct.
  • Will there ever be multiple missing numbers?
    • No.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Loop through the array from smallest to largest, and use a counter variable to try counting up with each element.

1) First, sort the array from smallest to largest
2) Create a counter variable starting at zero
3) For each element in the array
  a) Check if it matches the counter
  b) If it does, all is well -- so add 1 to the counter
  c) If not, this is the missing number, and the counter will stay as is
4) When the loop is finished, return the counter's value

I-mplement

# Example Input: nums = [3,0,1]
# Expected Output: 2

def find_missing(nums):
	nums.sort()
	counter = 0
	for num in nums:
		if num == counter:
			counter += 1 
	return counter

Alternatively, a slightly more efficient solution is possible using the break statement to exit the loop early once the missing number is found:

# Example Input: nums = [3,0,1]
# Expected Output: 2

def find_missing(nums):
	nums.sort()
	counter = 0
	for num in nums:
		if num == counter:
			counter += 1 
                else:
                        break # Do not need to keep looping
	return counter
Clone this wiki locally