CODEWITHSUNDEEP
pythonbitwise-operators
dpd
dpd

Reputation: 187

how to find out binary number similarity

Recently I have appeared in a coding challenge where one of the question is as below

There are N cars, each having some of M features. A car feature list is given as binary string.

for ex: 0000111

0 means feature not supported.

Two cars are similar if their feature description differs by atmost one feature. for ex: 11001, 11000 are similar for every car, find count of similar cars in a list of cars with features

I have tried to solve the problem with XOR operator. But it worked for few test cases

cars = ["100", "110", "010", "011", "100"]

Here for car at 0th index is similar to 1st and 4th. so output should be 2. similar for all the index car need to be found out with which it is similar.

Solution I tried:

def solution(cars):
    ret_list = []
    for i in range(len(cars)):
        count = 0
        for j in range(len(cars)):
            if i != j:
                if (int(cars[i]) ^ int(cars[j])) <= 100:
                    count += 1
        ret_list.append(count)
        print(ret_list)
    return ret_list

output : [2, 3, 2, 1, 2]

But this doesn't fit to when input is like:

cars = ["1000", "0110", "0010", "0101", "1010"]

Can someone please suggest a better solution that works for all kind of binary number

Upvotes: 1

Views: 596

Answers (2)

francof2a
francof2a

Reputation: 194

import numpy as np

# ...

# conversion to int
cars_int = np.array([int(c,2) for c in cars]).reshape(1,-1)

# matrix to compare all against all
compare = (cars_int ^ cars_int.T) # or exclusive

# result of cars with 0 or 1 hamming distance 
# (not including comparison of each car with itself)
result = (np.sum(compare & (compare-1) == 0) - cars_int.size) // 2

if you want a list with similarity by car:

# ...
result_per_car = np.sum(compare & (compare-1) == 0, axis=1) - 1

Upvotes: 0

user16004728
user16004728

Reputation:

Try this:

def isPowerOf2(x):
    return (x & (x - 1)) == 0

def areSimilar(x, y):
    return isPowerOf2(x ^ y)

def solution(cars):
    similarPairCount = 0
    for i in range(len(cars) - 1):
        for j in range(i + 1, len(cars)):
            if areSimilar(int(cars[i], 2), int(cars[j], 2)):
                similarPairCount += 1
    return similarPairCount

Upvotes: 2

Related Questions