Skip to content

Missing Number

  • Title: Missing Number
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1083
  • Secondary topics: Running total, long long discipline, Input fluency
  • Difficulty: easy
  • Subtype: Recover one missing value from the range 1..n
  • Status: solved
  • Solution file: missingnumber.cpp

Why Practice This

This is a strong first note for the repo because almost nothing here is algorithmically hard.

That is exactly the point.

It lets you practice the beginner loop cleanly:

  • read input without friction
  • choose a safe integer type
  • write one tiny invariant
  • compile and run without fighting syntax

If this problem still feels noisy, it usually means the local C++ workflow needs a little more repetition before harder topics.

Recognition Cue

Reach for this arithmetic-sum pattern when:

  • the values should be exactly one complete range
  • exactly one value is missing
  • order does not matter
  • you want the smallest possible implementation surface

The strongest smell is:

  • "numbers from 1..n, one missing"

That should suggest comparing an expected total against the observed total before using heavier containers.

Problem-Specific Transformation

The statement is rewritten as:

  • expected sum of 1..n
  • minus actual sum of the n-1 given values

So the problem stops being about searching an array and becomes one running-total identity.

That is why it is such a good early workflow note: the algorithm is trivial, but type choice and clean I/O still matter.

Core Idea

The numbers should be exactly:

1 + 2 + ... + n

but one value is missing from the input.

So:

  1. compute the expected total of 1..n
  2. subtract every value that actually appears
  3. the remaining value is the answer

The standard arithmetic-sum formula is:

n * (n + 1) / 2

That total should be stored in long long, not int, because the intermediate multiplication can exceed 32-bit range.

This is a great beginner habit:

  • the code is tiny
  • the variable meanings are simple
  • type discipline still matters

Complexity

  • one pass over the input: O(n)
  • memory: O(1)

Pitfalls / Judge Notes

  • Use long long for the running total and the expected sum.
  • The missing value is from 1..n, while the input contains only n - 1 numbers.
  • This is a perfect warm-up for the compile/run loop. Do not overengineer it with extra containers if you do not need them.

Reusable Pattern

Solutions