# KRYP4 - Editorial

[Contest][1]
[Practice][2]

Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]

CAKEWALK

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