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