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
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