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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution