# HackerRank ‘Sherlock and Pairs’ Solution

##### 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:
```#!/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)
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.