Problem of the Day
A new programming or logic puzzle every Mon-Fri

You are given an array of unsorted integers between 1 and 1,000,000, however, one number is missing. Write a program to determine which number is missing from the array? Can you solve this in linear runtime?

Comments:

• Adam - 10 years, 3 months ago

  expected_sum = (1 + 1000000) * (500000) array_sum = sum(xs) missing = expected_sum - array_sum

  reply permalink

• Max Burstein - 10 years, 3 months ago

  I like this approach. Good stuff

  reply permalink

• Karl - 10 years, 3 months ago

  Very nice for this problem yes (elegant, even), but what about two missing numbers?

  The codified solutions could be easily modified to find both.

  reply permalink

• Foppe - 10 years, 3 months ago

  #! /usr/bin/pyton
  
  import random
  
  # Sum of integers 1 ... 1,000,000
  sum_of_all_integers = (1000000 + 1) * (1000000 / 2)
  
  # Create array with one item missing
  array_of_integers = []
  for i in range(1, 1000001):
      array_of_integers.append(i)
  random_number_missing = random.randint(1,1000000)
  array_of_integers.remove(random_number_missing)
  random.shuffle(array_of_integers)
  
  # Sum elements in array
  sum_of_integers = 0
  for i in array_of_integers:
      sum_of_integers += i
  
  # Subtract sum of array with missing number from
  # sum of array wth all numbers
  missing_number = sum_of_all_integers - sum_of_integers
  
  # Test
  print("Expected: %d" % random_number_missing)
  print("Calculated: %d" % missing_number)
  

  reply permalink

• Beginner - 10 years, 3 months ago

  Would anyone care to explain what linear run time is? All the websites I've looked at assume I know too much.

  reply permalink

• Foppe - 10 years, 3 months ago

  Big Oh notation states "how well an algorithm scales as data(ponts) increases". Linear being almost optimal as run-time means you run only one time over the data as shown in my solution above. The array is traversed only once for adding all integers. A less optimal solution (n log n) would start with sorting the array then picking the missing number. You'd need to traverse the array more than once to sort it en then traverse it again to find the missing integer. Optimisation of algorithms is important when dealing with lhuge data-sets. One million integers is relatively not large.

  reply permalink

• Anonymous - 10 years, 3 months ago

  Basically only looking at each number in the array once

  reply permalink

• wobblebucket - 10 years, 3 months ago

  import random
  total = 499999500000L
  mystery = range(1, 1000000)
  mystery.remove(random.randint(1,1000000))
  print total - sum(mystery)
  

  reply permalink