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.

70 lines
2.5KB

  1. from fractions import gcd
  2. """
  3. Ah, combinatronics maths, always fun.
  4. Let's suppose we have two guards starting with a and b bananas, where we assume a > b
  5. Let k be the largest positive integer such that a > (2^k - 1)b
  6. If a = b(2^k - 2^(m-1) - 1) or a = b(2^(k+1) - 2^m - 1) for some integer m between 0 and k included
  7. then we can match the two guards to play an infinite round of thumb wrestling.
  8. We can thus deduce the formula below after development.
  9. """
  10. def loops(x, y):
  11. res = (x+y)/gcd(x,y)
  12. return bool(res & (res - 1))
  13. """
  14. This function might looks like a bottleneck but we need to find a
  15. way to update node sizes either way, so i don't think a better way
  16. is possible at the time of writing. I might totally be wrong but for our use
  17. case arrays won't be bigger than 100 so *shrug*
  18. """
  19. def remove(guards, ref):
  20. for i in range(len(guards)):
  21. j = 0
  22. while j < len(guards[i]):
  23. if(guards[i][j]==ref):
  24. guards[i].pop(j)
  25. j+=1
  26. guards[ref]=[-1]
  27. def answer(banana_list):
  28. guards= [[] for i in range(len(banana_list))]
  29. bad=0
  30. for i in range(len(guards)):
  31. for j in range(len(guards)):
  32. if(loops(banana_list[i], banana_list[j])):
  33. guards[i].append(j)
  34. to_process=len(banana_list)
  35. while(to_process>0):
  36. # we first find the lesser used number
  37. min_num=0
  38. for i in range(len(guards)):
  39. if(i!=0 and (len(guards[i])<len(guards[min_num]) or guards[min_num]
  40. == [-1]) and guards[i]!=[-1]):
  41. min_num=i
  42. # if this node absolutely cannot be paired we purge it
  43. if((len(guards[min_num])) == 0 or (len(guards[min_num])==1 and
  44. guards[min_num][0] == guards[min_num]) and guards[min_num] !=
  45. [-1]):
  46. remove(guards, min_num)
  47. to_process-=1
  48. bad+=1
  49. else:
  50. # now we deduce the lesser used node associated to this number
  51. min_node=guards[min_num][0]
  52. for i in range(len(guards[min_num])):
  53. if(i!=0 and guards[min_num][i]!=min_num and len(guards[guards[min_num][i]])<len(guards[min_node])):
  54. min_node=guards[min_num][i]
  55. # if we fail here infinite loop, which is bad because that means
  56. # only processed nodes exist and we haven't exited; logic bug
  57. if(guards[min_node]!=[-1]):
  58. remove(guards, min_num)
  59. remove(guards, min_node)
  60. to_process-=2
  61. return bad