DSA sheet / Sorting and searching
Distinct Numbers
The problem in brief
You are given n integers (n up to 200 000, each up to 10^9). Print how many distinct values there are among them.
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/1621.
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.
-
Comparing every pair of numbers would be far too slow at this size. What structure answers “have I seen this value before?” quickly?
-
Alternatively, imagine the numbers written in sorted order. Where would equal values end up, and how would you count groups of them?
-
In a sorted list, a value is “new” exactly when it differs from the one just before it. Which of the two ideas do you prefer, and what does each cost?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Start with the naive version: for each number scan everything before it, O(n^2), about 4 * 10^10 steps. That fails, and the reason it is slow is that it repeats work: each membership test rescans history. Any fix must make membership cheap.
There are two standard ways to get there and both are worth knowing. Hashing gives expected O(1) membership: insert into a set and the set’s size is the answer. Sorting gives grouping for free: after sorting, duplicates are adjacent, so a single pass counting “differs from previous” finishes the job in O(n log n). Neither dominates: hashing is shorter, sorting has no adversarial-collision risk and works on languages without a good hash set.
The habit: whenever a question is about equality or duplicates, reach for a set or a sort before anything else.
Intuition
Dump all the numbers into a bag that refuses duplicates; count what is inside. Or line the numbers up in order and count how many times the value changes, plus one.
Approach
- Read the n values.
- Sort them (or insert them into a hash set).
- Count the positions i where value[i] differs from value[i - 1], plus one for the first element (or take the set’s size).
- Print the count.
Pitfalls: values reach 10^9, which fits in a 32-bit signed int, but be careful to read n before the values. In Java, sorting a primitive int[] uses a dual-pivot quicksort that adversarial inputs can push to quadratic time, so shuffle first or use a HashSet. The Java version below uses a hash set.
Complexity
Sorting: O(n log n) time, O(n) memory. Hash set: expected O(n) time, O(n) 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);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
cout << (unique(a.begin(), a.end()) - a.begin()) << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
print(len(set(data[1:1 + int(data[0])])))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
HashSet<Integer> seen = new HashSet<>();
for (int i = 0; i < n; i++) {
st.nextToken();
seen.add((int) st.nval);
}
System.out.println(seen.size());
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean);
const n = Number(data[0]);
console.log(new Set(data.slice(1, 1 + n).map(Number)).size);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).