# Sherlock and Pairs

See the original problem on HackerRank.

## Solutions

### Sort

C++ solution using sorting ($$O(N \cdot logN)$$:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  int T, N; cin >> T; while (T--) { cin >> N; vector nums; nums.reserve(N); copy_n(istream_iterator(cin), N, back_inserter(nums)); sort(begin(nums), end(nums)); auto it = begin(nums); unsigned long long pairs = 0; while (it != end(nums)) { auto ub = find_if(it, end(nums), [&](int i){ return i!=*it; }); const auto dist = distance(it, ub); pairs += (dist*(dist-1)); it = ub; } cout << pairs << endl; } 

 1 2 3  countPairs :: [Int] -> Int countPairs = sum . fmap (\x -> x * (x - 1)) . filter (> 1) . fmap length . group . sort

Ruby solution by [Andrea Casarin]()

 1 2 3 4 5 6 7  def count_pairs(a) return a .group_by(&:itself) .transform_values!(&:size) .values.map{|x| x * (x-1)} .sum end

Javascript solution by Davide Trevisan

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  function solve(a) { var k = 0; a.sort(); for (var i = 0; i < a.length; i++) { var count = 1; for (var j = i + 1; j < a.length; j++) { if (a[i] === a[j]) count++; else break; } i += count > 1 ? count - 1 : 0; if (count > 1) k += count * (count - 1); } return k; } 

### Frequency table (hash map)

 1 2 3 4 5 6 7  import Data.HashMap.Strict (fromListWith, elems) frequency :: [Int] -> [Int] frequency xs = elems (fromListWith (+) [(x, 1) | x <- xs]) countPairs :: [Int] -> Int countPairs = sum . fmap (\x -> x * (x - 1)) . filter (> 1) . frequency

Python solution by Marco Ferrati

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  def solve(a): maxPairs = 0 d = {} for i in range(0, len(a)): d[a[i]] = 0 for i in range(0, len(a)): d[a[i]] += 1 for key, value in d.items(): if value <= 1: pass else: maxPairs += value * (value-1) return maxPairs

### Frequency table (array)

A more efficient solution uses extra space. Instead of sorting, we fill a frequency table with element frequencies:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  int T, N, i; cin >> T; while (T--) { cin >> N; array freq{}; while (N--) { cin >> i; freq[i]++; } unsigned long long pairs = 0ull; for (auto j : freq) { pairs += (unsigned long long)j*(j-1); } cout << pairs << endl; } 

The reduce sequence can be replaced with accumulate:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  int T, N, i; cin >> T; while (T--) { cin >> N; array freq{}; while (N--) { cin >> i; freq[i]++; } cout << accumulate(begin(freq), end(freq), 0ull, [](auto pairs, unsigned long long curr){ return pairs + curr * (curr-1); }) << "\n"; } 

Notes:

• 64bit integers are needed (that why there is an explicit commit to unsigned long long in the lambda second parameter)
• if the stack memory is smaller, array must be replaced with vector
We've worked on this challenge in these gyms: modena  padua