Deloitte | COGNIZANT | IBM | CAPGEMINI
def generateBinaryPathCode(n):
def flip_tracker():
return [True] * n
def bit_diff(a, b):
return bin(a ^ b).count('1')
def get_bit_flipped_index(a, b):
return (a ^ b).bit_length() - 1
def backtrack(path, used, direction):
if len(path) == 2 ** n:
if bit_diff(path[-1], path[0]) == 1:
return path
return None
last = path[-1]
for i in range(n):
mask = 1 << i
if direction[i]:
candidate = last | mask
else:
candidate = last & ~mask
if candidate not in used:
direction[i] = not direction[i]
path.append(candidate)
used.add(candidate)
result = backtrack(path, used, direction)
if result:
return result
path.pop()
used.remove(candidate)
direction[i] = not direction[i]
return None
return backtrack([0], {0}, flip_tracker())
#generateBinaryPath
#IBM
689 ·