My solutions for google foobar
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

26 lines
908 B

"""
Logic is pretty much self explained there, complexity should be also fairly low,
but heck was it tricky
"""
def answer(n):
# n is given as a string so let's cast it
n=int(n)
res = 0
while(n!=1):
# if our number is odd then let's just divide by 2
if(n%2==0):
n=n/2
# now this is the tricky part and took me a bunch of googling to figure
# out: instead of going the brute force O(n²) way and just trying out
# every possibility in nested loops you can actually figure out if you
# should add or remove: when rightmost bits are set as "111" the
# preferred operation is to add, as that would push back everything as
# 000s, while any other case would be faster the other way around.
elif((n==3) or ((n+1)&n) > ((n-1)&(n-2))):
n-=1
else:
n+=1
res+=1
return res