# HackerRank ‘Sherlock and Pairs’ Solution

H
##### Short Problem Definition:

Sherlock is given an array of N integers A0, A1 … AN-1 by Watson. Now Watson asks Sherlock how many different pairs of indices i and j exist such that i is not equal to j but Ai is equal to Aj.

That is, Sherlock has to count total number of pairs of indices (i, j) where Ai = Aj AND i ≠ j.

Sherlock and Pairs

##### Complexity:

time complexity is O(n)

space complexity is O(n)

##### Execution:

The first step is to create a count of all integers. Next there are choose(k,2)*2 distinct pairs for each integer count (this step similar to Handshake, but you count i,j and j,i as two distinct pairs). Count those together and you arrive at the answer.

##### Solution:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `#!/usr/bin/py` `def` `cnt_equals(arr):` `    ``the_map ``=` `{}` `    ``final_cnt ``=` `0` `    ``for` `value ``in` `arr:` `        ``if` `value ``not` `in` `the_map:` `            ``the_map[value] ``=` `1` `        ``else``:` `            ``the_map[value] ``+``=` `1`   `    ``for` `value ``in` `the_map.values():` `        ``if` `value !``=` `1``:` `            ``final_cnt ``+``=` `(value``*``(value``-``1``))`   `    ``return` `final_cnt`   `if` `__name__ ``=``=` `'__main__'``:` `    ``t ``=` `input``()` `    ``for` `_ ``in` `xrange``(t):` `        ``n ``=` `input``()` `        ``arr ``=` `map``(``int``, ``raw_input``().split())` `        ``print` `cnt_equals(arr)` 