281. How Many Different Values
Foundation1000 ms256 MBSolved by 0%
Print how many DIFFERENT values appear among n integers.
The direct approach checks each value against everything before it, which is
about n^2 / 2 comparisons. At 200000 that is twenty billion and the largest
test will not finish.
A set answers "have I seen this before" without searching. Insert every value and the answer is how many the set holds, since a set ignores repeats by definition.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the number of distinct values.
Input4
1 2 2 3
Output3
Notehas one repeated value
Input1
1
Output1
Noteis a single element
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.