###
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:**
- Count the sum of all numbers you have. Let it be 5027, for example.
- Sum of natural numbers from 1 to N, can be expressed as
**N * (N + 1) / 2**, i.e. 100 * (100 + 1) / 2 = 5050.
- 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