The lost sheep: finding the missing number

What man of you, having an hundred sheep, if he lose one of them, doth not leave the ninety and nine in the wilderness, and go after that which is lost, until he find it? — Luke 15:4 (KJV)

Jesus told this story to people who were grumbling that he spent time with sinners. The shepherd doesn’t shrug and keep the ninety-nine. He counts, notices one is missing, and goes after it until he finds it — “and when he hath found it, he layeth it on his shoulders, rejoicing” (Luke 15:5).

Programmers get a puzzle with exactly the same shape.

The puzzle

You’re given a list of the numbers 1 to 100, in any order, with one missing. Find it.

flock = [12, 87, 3, 55, ...]   # 99 numbers; one of 1..100 is gone

The slow way: check every sheep against the whole flock

def find_missing_slow(nums):
    for k in range(1, len(nums) + 2):
        if k not in nums:          # scans the whole list each time
            return k

It works, but k not in nums walks through the list every time. For 100 numbers that’s up to 100 × 100 — almost ten thousand checks. For a million numbers it’s a trillion. We say this takes O(n²) time: double the flock, four times the work.

The shepherd’s way: count

A shepherd doesn’t compare every sheep with every other sheep. He knows how many there should be.

Here’s the trick: 1 + 2 + 3 + … + 100 always equals 5,050. Pair the numbers from both ends — 1 + 100, 2 + 99, 3 + 98 — and every pair makes 101. There are 50 pairs, so 50 × 101 = 5,050. In general, the numbers 1 to n add up to n × (n + 1) ÷ 2.

So:

1. Work out what the total should be: 5,050.
2. Add up the flock you actually have — say it comes to 5,013.
3. The difference is your lost sheep: 5,050 − 5,013 = 37.

The code

def find_missing(nums):
    n = len(nums) + 1                 # how many there should be
    expected = n * (n + 1) // 2       # the total if none were missing
    return expected - sum(nums)       # what's missing

find_missing(flock)   # 37

One pass through the list to add it up — O(n) time — and only a couple of numbers stored — O(1) space.

function findMissing(nums) {
  const n = nums.length + 1;
  const expected = (n * (n + 1)) / 2;
  return expected - nums.reduce((total, x) => total + x, 0);
}

In an interview

This is a classic. Things worth saying out loud:

• Ask about the range. It’s often asked as 0 to n instead of 1 to n. Then n = len(nums) and the formula is the same.
• Mention a second way. A set also works in O(n) time — set(range(1, n + 1)) - set(nums) — but it uses O(n) extra memory. The sum trick doesn’t.
• Overflow. Python integers never overflow. In Java or C, n * (n + 1) can overflow for huge n; use a 64-bit type, or the XOR trick (XOR all of 1..n with all the numbers; pairs cancel and the missing one remains).

Common mistakes

• Off by one. The list has 99 numbers but the range is 1 to 100, so n = len(nums) + 1, not len(nums).
• Using / in Python. / gives a float (5050.0). Use // for whole-number division.
• Sorting first. Sorting and scanning works too, but sorting costs O(n log n) — more than you need.

Try it

1. Run find_missing on list(range(1, 101)) with 37 removed. Then remove 1, and then 100 — does it still work at the edges?

2. Change the function for the 0 to n version of the puzzle.

3. Two sheep are missing. The sum tells you their total. What second thing could you add up to find both?

   Hint

   Add up the squares too. Now you know a + b and a² + b² — two equations, two unknowns.

Reflect

The shepherd could have done the maths and called ninety-nine good enough. He didn’t. “Likewise joy shall be in heaven over one sinner that repenteth, more than over ninety and nine just persons” (Luke 15:7). Every single one counts.