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.

27 lines
908B

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