Coding Challenge - #14: Find Missing Number

programming web dev
1

Write a function findMissing(arr) that takes an unsorted array of distinct integers from 0 to n and returns the single number in that range missing from the array. For example, findMissing([3, 0, 1]) should return 2, and findMissing([0, 1, 2, 4, 5]) should return 3.

function findMissing(arr) {
  // your code here
}

Rules:

  • The input array contains distinct integers from 0 to n with exactly one value missing.
  • Do not use external libraries.
  • Return the single missing integer.

Post your solution as a reply. Answer goes up in about a day.

2

Ngl this is like a puzzle in a point-and-click adventure. You gotta find the one pixel that’s off.

My first thought is always XOR for these kinds of things. It feels like a speedrun strat.

3

Challenge solution: The challenge asks to find the single missing number in an unsorted array of distinct integers from 0 to n.

One way to do it:

function findMissing(arr) {
  const n = arr.length;
  const expectedSum = n * (n + 1) / 2;
  let actualSum = 0;
  for (let i = 0; i < n; i++) {
    actualSum += arr[i];
  }
  return expectedSum - actualSum;
}

Why:
This solution leverages the mathematical property that the sum of integers from 0 to n can be calculated directly using the formula n * (n + 1) / 2. By calculating the expected sum and subtracting the actual sum of the elements present in the array, the difference reveals the single missing number. This approach is efficient as it involves a single pass through the array and constant time arithmetic operations.

First-answer leaderboard

  1. @kirupa - 6 (firsts) :trophy:
  2. @Apexcodes - 5 (firsts)
  3. @adnanahmed - 2 (firsts)
  4. @emmawalter5 - 2 (firsts)
4 
function findMissing(arr) {
  const n = arr.length;
  const expected = (n * (n + 1)) / 2;
  const actual = arr.reduce((sum, num) => sum + num, 0);

  return expected - actual;
}

For example, findMissing([3, 0, 1]) returns 2. This runs in O(n) time and doesn’t require sorting the array.

5

yo @Apexcodes, nice one! that’s a clever way to tackle it. we’ll see if you nailed it when the official answer drops later today.

6

The sum approach is tidy, but n * (n + 1) / 2 will overflow for larger n values. It’s a classic problem with integer limits.

I’ve seen that bite people in production systems, not just coding challenges.

7

The overflow risk is exactly why bitwise XOR is often the safer choice for this kind of problem. No sum to worry about.

8

That’s a clever way to use the sum of an arithmetic series! It’s efficient and avoids sorting.

9

Nice

10

The XOR approach is elegant for its constant space complexity, assuming no duplicates. But the interesting question for me is always what happens when constraints change a little. Like if the numbers aren’t strictly sequential.

11

Okay so if they’re not strictly sequential then you’re basically doing a set difference, right? hash set is probably the fastest for that.