Bitwise Pairs

Accenture coding challenges question, verified with a worked answer. Free to practise - no sign-up.

Input format

The first line contains an integer n. The second line contains n space-separated integers representing the array nums.

Output format

A single integer representing the number of valid pairs.

Constraints

1 <= n <= 10^5
0 <= nums[i] <= 10^9

Sample tests

Input
4
1 2 3 4

Expected
1

Input
5
4 5 6 7 8

Expected
6

def bitwise_pairs(nums):
    from collections import defaultdict
    groups = defaultdict(int)
    for num in nums:
        if num == 0:
            groups[0] += 1
        else:
            groups[num.bit_length()] += 1
    total = 0
    for count in groups.values():
        total += count * (count - 1) // 2
    return total