Missing Number

This is LeetCode 268: given an array nums of n distinct numbers in the range $[0,n]$, find the only number in that range that is missing from the array. For example, for nums = [3, 0, 1] the answer is 2.

MissingNumber

template MissingNumber(n) {
  signal input nums[n];
  signal output out;

  // without these checks, `out` would be meaningless for an invalid `nums`
  for (var i = 0; i < n; i++) {
    AssertInRange(0, n)(nums[i]);
  }
  AssertDistinct(n)(nums);

  // the missing number is the sum of 0, 1, ..., n minus the sum of `nums`
  var sum = 0;
  for (var i = 0; i < n; i++) {
    sum += nums[i];
  }
  out <== n * (n + 1) \ 2 - sum;
}

The Famous Trick

The well-known solution is a one-liner. The numbers $0,1,\dots ,n$ add up to $n(n+1)/2$, and exactly one of them is missing from nums, so:

$$\text{missing}=\frac{n(n+1)}{2}-\sum _i\text{nums}[i]$$

This is even better in a circuit than on a CPU: it is only additions and a constant, so it costs zero non-linear constraints!

template MissingNumber(n) {
  signal input nums[n];
  signal output out;

  var sum = 0;
  for (var i = 0; i < n; i++) {
    sum += nums[i];
  }
  out <== n * (n + 1) \ 2 - sum;
}

We use \, which is integer division in Circom, instead of /, which is division in the field. The two agree here because $n(n+1)$ is always even.

The Catch

On LeetCode, the input is guaranteed to be valid. In a circuit, nothing is guaranteed: whoever creates the proof also picks the input. The circuit above returns some number for any array, valid or not. For example, with $n=3$ we have $n(n+1)/2=6$, and:

• nums = [0, 0, 4] gives 2, but 4 is out of range and 0 is repeated.
• nums = [1, 4, 1] gives 0, which is not even missing from a valid point of view.

A proof that “the missing number is 2” would be meaningless here. So, just like the magic square, we must check the input as well:

• every number is in range $[0,n]$, using AssertInRange,
• all numbers are distinct, using AssertDistinct.

With these, nums is exactly $\{0,1,\dots ,n\}$ with one number removed, and the formula gives the right answer.

Constraint Count

The formula is free, but the checks are not. AssertDistinct compares every pair of numbers, so the cost grows quadratically:

For $n=100$, 9900 of these come from AssertDistinct and 1400 from the range checks. The famous trick that makes this problem “easy” is not where the work is: in a circuit, most of the cost goes into making sure that the input actually satisfies the assumptions of the problem.