[Contest][1]
[Practice][2]
Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]
DIFFICULTY
CAKEWALK
PREREQUISITES
Basic Maths
PROBLEM
Given a list of integers, the aim is to find out the number of ways to select two integers having the same value.
EXPLANATION
For a given value, let the number of integers be X.
The number of ways to select two of them is Y= {X\choose 2}.
The answer is the summation of this Y for all distinct values present in the list provided.
This can be done by making use of a map to keep track of frequencies of all the distinct values.
The complexity of accessing/inserting elements in the map is O (Log (N)).
Hence the total complexity turns out to be O (N \hspace{1 mm}Log (N)).
SOLUTION
Setter’s Solution -
[5]
[1]: https://www.codechef.com/CODR2018/problems/KRYP4
[2]: https://www.codechef.com/problems/KRYP4
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: https://www.codechef.com/viewsolution/17468659