Bitwise AND - Hackerrank Intermediate Skills Python Solution

Bitwise AND - Problem Solving Intermediate 

Given an array of non-negative integers, count the number of unordered pairs of array elements such that their bitwise AND is a power of 2.

For example, let's say the array is arr = [10, 7, 2, 8, 3), and let '&' denote the bitwise AND operator. There are 6 unordered pairs of its

elements that have a bitwise AND that is a power of two:

For indices (0,1), 10 & 7 = 2, which is a power of 2.

For indices (0,2), 10 & 2 = 2, which is a power of 2.

For indices (0,3), 10 & 8 = 8, which is a power of 2.

For indices (0,4), 10 & 3 = 2, which is a power of 2.

For indices (1,2), 7 & 2 = 2, which is a power of 2.

For indices (2,4), 2 & 3 = 2, which is a power of 2.

Therefore, the answer is 6.

Function Description

Complete the function countPairs in the editor below.

countPairs has the following parameter:

int arr[n]: an array of integers

Returns:

int: the number of unordered pairs of elements of arr such that their bitwise AND is a power of 2

Constraints

• 1sns 2*105

• Os arr[i]< 212

Input Format For Custom Testing

The first line contains an integer, n, denoting the number of elements in arr.

Each line i of the n subsequent lines (where 0 si<n) contains an integer describing arr[i].

Sample Case 0

Sample Input For Custom Testing

STDIN

Function

4

n = 4

arr = [1, 2, 1, 3]

1

=>

2

1

3

Sample Output

4

Explanation

All unordered pair of elements whose bitwise AND is a power of 2 are:

For indices (0,2), 1 & 1 = 1, which is a power of 2.

• For indices (0,3), 1 & 3 = 1, which is a power of 2.

For indices (1,3), 2 & 3 = 2, which is a power of 2.

For indices (2,3), 1 & 3 = 1, which is a power of 2.

Therefore, the answer is 4.

Sample Case 1

Sample Input For Custom Testing

3

0

2

4

Sample Output

0

Explanation

There are no pairs of array elements such that their bitwise AND is a power of 2. Therefore, the answer is 0.

Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

from collections import defaultdict

#
# Complete the 'countPairs' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def countPairs(arr):
    po2 = lambda x: x > 0 and not (x & (x - 1))
    d = defaultdict(int)
    for x in arr:
        d[x] += 1
    d = list(d.items())
    ans = 0
    for i in range(len(d)):
        a, a_cnt = d[i]
        for j in range(i, len(d)):
            b, b_cnt = d[j]
            if po2(a & b):
                if a == b:
                    ans += (a_cnt * (a_cnt - 1)) // 2
                else:
                    ans += a_cnt * b_cnt
    return ans          

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr_count = int(input().strip())

    arr = []

    for _ in range(arr_count):
        arr_item = int(input().strip())
        arr.append(arr_item)

    result = countPairs(arr)

    fptr.write(str(result) + '\n')

    fptr.close()

Ps: The Question is Generated by Hackerrank. We Only Provide/Write Answer of the Given Problems for Educational Purpose Only. Any Queries Regarding Question Drop your Queries  Here