Count pairs of numbers with equal number of ones in their binary representation-CodePudding

Given an array of positive integers a, your task is to count the number of pairs i and j (where 0 ≤ i < j < a.length), such that a[i] and a[j] have the same number of 1s in their binary representations.

constraint size(a)<10^9

Example

input=[3,4,5,6,1,2]

ans=6

possible pairs=[(3,5)(3,6)(5,6)(4,1)(4,2)(1,2)]

My Sol:

def numPairs(input):
    count=0
    for i in range(0,len(input)):
        for j in range(i 1,len(input)):
            if bin(input[i]).count('1')==bin(input[j]).count('1'):
                count =1
    return count

This solution gives time limit error

Can we convert this solution in 1 loop like two-sum?

CodePudding user response：

from collections import Counter

def num_pairs(input_arr): 
    res = 0 
    counter = Counter() 
    for el in input_arr: 
        num_ones = bin(el).count("1") 
        res  = counter[num_ones] 
        counter[num_ones]  = 1 
    return res

This solution runs in O(n) time and O(log n) space, if we consider the counting operation of ones in each number constant. Otherwise we can say that it runs in O(n log n) time since we need log n operations to count the number of ones in each number.

This is indeed a variation of the two sum problem where the pairing criteria as been changed to having the same number of ones in the binary representation of the number.

Your current solution is of quadratic time complexity. You could still do some small optimization by saving the count of ones in input[i] while comparing it with all the following input[j]s.

CodePudding user response：

bin() function returns a binary string of given number. count("1") to get the number of 1's in binary representation and from that list, find the number of combinations.

Here is the solution

def numPairs(inputs):
    sum=0
    L = list(map(lambda x: bin(x).count("1"), inputs))
    for i in range(max(L) 1):
        c=L.count(i)
        if c>1:
            sum  = c*(c-1)/2
    return int(sum)

Or could go crazier and make a one-liner solution. This is as efficient as it gets for pure python solution. especially space-wise since it doesn't construct a list. time complexity would be O(n).

from collections import Counter
from functools import reduce

def numPairs(inputs):
    return int(reduce(lambda x,y: x y, map(lambda x: x*(x-1)/2, Counter(map(lambda x: bin(x).count("1"), inputs)).values())))

print(numPairs([3,4,5,6,1,2])) # prints 6