Skip to content

Distinct Numbers

Why Practice This

This is a great first STL note because the whole problem is smaller than the toolbox choice:

  • do we use set?
  • do we sort and call unique?
  • do we reach for hashing?

That is exactly the kind of decision basic STL fluency should make feel natural.

Recognition Cue

Reach for sort + unique when:

  • you only need the number of distinct values
  • original order is irrelevant
  • duplicates are defined by plain value equality

The strongest smell is:

  • "count how many different numbers appear"

That is often easier with one sorted vector pass than with a heavier container.

Problem-Specific Transformation

The statement is rewritten as:

  • sort values so equal ones become consecutive
  • compress each equal block to one representative

So the problem becomes:

  • one sorting pass
  • one deduplication pass

That turns the whole task into a small STL workflow exercise rather than custom counting logic.

Core Idea

One clean solution is:

  1. read the numbers into a vector
  2. sort the vector
  3. call unique
  4. count how many values remain

After sorting, equal values become consecutive. unique then compacts the vector so only one representative of each equal block stays in the prefix.

So the number of distinct values is:

unique_end - values.begin()

This is a nice STL-basics exercise because the real work is done by standard algorithms rather than custom logic.

A set or unordered_set would also work, but sort + unique is especially educational here because it teaches two very common contest tools at once.

Complexity

  • sorting: O(n log n)
  • unique: O(n)
  • total: O(n log n)

Pitfalls / Judge Notes

  • unique does not erase elements by itself; it returns the new logical end iterator.
  • Always sort before using unique if you want to remove all duplicates by value.
  • This problem only asks for the count, so you do not need to preserve original order.

Reusable Pattern

Solutions