Home
hackerrank
hackerrank certification

Bitwise And - Problem Solving (Intermediate) | HackerRank

 


Bitwise AND 


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 


Solution in Python:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#!/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()

Labels : #hackerrank ,#hackerrank certification ,#problem solving (intermediate) ,#python ,

Post a Comment