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
res = 0
# if our number is odd then let's just divide by 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))):
return res