Deloitte | COGNIZANT | IBM | CAPGEMINI
def generateBinaryPathCode(n):
t = 1 << n
l = []
s = set()
dp = [0] * n
def isValid(prev, curr):
d = prev ^ curr
if bin(d).count('1') != 1:
return False
b= d.bit_length() - 1
tb = (curr >> b) & 1
k = 1 if dp[b] % 2 == 0 else 0
return tb == k
def backtrack():
if len(l) == t:
return bin(l[0] ^ l[-1]).count('1') == 1
prev = l[-1]
for i in range(n):
b = 1 << i
c = prev ^ b
if c in s:
continue
if not isValid(prev, c):
continue
l.append(c)
s.add(c)
dp[i] += 1
if backtrack():
return True
l.pop()
s.remove(c)
dp[i] -= 1
return False
l.append(0)
s.add(0)
if backtrack():
return l
return []
7/7 cases passed✅✅
contact : @MLCODER2
761 ·