[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
```