Find the missing number in one pass

Question

Someone reads out the whole numbers from 1 to 100 in a random order, except that one number is left out. You hear the 99 numbers once each and cannot write them down; you may keep only a single running number in your head. 1. How do you identify the missing number? 2. Now suppose two numbers are missing. What two running quantities let you recover both?

Accepted Answer

Keep a running total of everything you hear; the missing number is 5,050 minus that total. One missing number. The numbers 1 to 100 add up to 100 × 101 / 2 = 5,050. If you add up the 99 numbers you hear and get S, the missing one is 5,050 minus S. You only ever need to remember the current total. Two missing numbers. Keep two running totals: the sum S of what you hear, and the sum Q of the squares of what you hear. The two missing numbers a and b then satisfy a + b = 5,050 minus S, and a squared + b squared = 338,350 minus Q, where 338,350 is the sum of the squares of 1 to 100 (the formula is…

Find the missing number in one pass

Your answer

Discussion

Learn the concepts

Related questions