Algorithms / How to find a missing number in sequence 1..100

Task description:

Suppose you have an array of 99 numbers. The array contains the digits 1 to 100 with one digit missing. How to find the missing digit?

Solution:
  1. Count the sum of all numbers you have. Let it be 5027, for example.
  2. Sum of natural numbers from 1 to N, can be expressed as N * (N + 1) / 2, i.e. 100 * (100 + 1) / 2 = 5050.
  3. Subtract the sum of the numbers from the result of step 2. 5050 - 5027 = 23 <= this is the missing number.
You can do this in O(n).

No comments:

Post a Comment