DSA sheet / Introductory
Missing Number
The problem in brief
You are given n, then n - 1 distinct integers, all taken from 1 to n. Exactly one number from that range is missing; print it. n can be as large as 200 000.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1083.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
You do not need to know which numbers are present in what order. Ask what you would know if the list were complete, and what changes when one value disappears.
-
The full list 1..n has a closed-form total. Compare it with the total of what you were given.
-
Check the size of that total for the largest n. Does it fit in a 32-bit signed integer?
-
There is a second trick with no overflow at all: XOR everything you have with everything you would expect. What does a value XORed with itself give?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The brute force is to mark every number you see in a boolean array and scan for the unmarked one. That is O(n) time and memory and it works. The habit worth building is asking “can I keep a single summary of the whole input instead of the input itself?”. The set of present numbers is a lot of information; you only need one number out of it.
Whenever a problem says “exactly one thing is different from a known baseline”, a running aggregate (sum, XOR, count) of the baseline minus the same aggregate of the data isolates the difference. That is the pattern: compute the aggregate of what should be there, subtract or cancel what is there.
Intuition
Imagine paying a bill of 1 + 2 + … + n and being handed all the coins but one. The shortfall is exactly the missing coin. XOR works like a “cancelling” version of the same idea: every number that appears twice (once in the expected list, once in the data) vanishes, and only the missing one is left.
Approach
- Read n and compute expected = n(n + 1) / 2 in a 64-bit integer.
- Read the n - 1 numbers, subtracting each from expected (or adding them to a running sum).
- What remains is the missing number.
Pitfall: n(n + 1)/2 is about 2 * 10^10 for n = 200 000, which overflows a 32-bit int. Use long long / long. Python is safe by default, and JavaScript numbers hold integers exactly up to 2^53, so they are fine here too. The XOR version avoids the issue entirely because the result never exceeds n.
Complexity
O(n) time to read the input, O(1) extra memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
long long rest = n * (n + 1) / 2;
for (int i = 0; i < n - 1; i++) {
long long x;
cin >> x;
rest -= x;
}
cout << rest << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
print(n * (n + 1) // 2 - sum(map(int, data[1:])))
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
long n = (long) st.nval;
long rest = n * (n + 1) / 2;
for (int i = 0; i < n - 1; i++) {
st.nextToken();
rest -= (long) st.nval;
}
System.out.println(rest);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
let rest = (n * (n + 1)) / 2;
for (let i = 1; i < data.length; i++) rest -= data[i];
console.log(rest);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).