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<int> nums; nums.reserve(N);
    copy_n(istream_iterator<int>(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;
}

Haskell solution by Alessandro Pezzato

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<int, 1'000'000+1> 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<int, 1'000'000+1> 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  milan 
comments powered by Disqus