##### 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.

##### Link

##### 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.