313. How Many Equal Pairs
Foundation1000 ms256 MBSolved by 0%
Print how many pairs of positions (i, j) with i < j hold equal values.
1 2 1 2 1 -> 4
The three ones give three pairs and the two twos give one, so four in total.
Counting the pairs directly is quadratic. Count each value instead: a value
appearing c times contributes c * (c - 1) / 2 pairs, and adding those up
over the distinct values is linear.
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 index pairs holding equal values.
Input5
1 2 1 2 1
Output4
Noteis the worked example, mixing two repeated values
Input1
1
Output0
Noteis a single element, which forms no pair
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.