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.
 

69 lines
2.5 KiB

from fractions import gcd
"""
Ah, combinatronics maths, always fun.
Let's suppose we have two guards starting with a and b bananas, where we assume a > b
Let k be the largest positive integer such that a > (2^k - 1)b
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
then we can match the two guards to play an infinite round of thumb wrestling.
We can thus deduce the formula below after development.
"""
def loops(x, y):
res = (x+y)/gcd(x,y)
return bool(res & (res - 1))
"""
This function might looks like a bottleneck but we need to find a
way to update node sizes either way, so i don't think a better way
is possible at the time of writing. I might totally be wrong but for our use
case arrays won't be bigger than 100 so *shrug*
"""
def remove(guards, ref):
for i in range(len(guards)):
j = 0
while j < len(guards[i]):
if(guards[i][j]==ref):
guards[i].pop(j)
j+=1
guards[ref]=[-1]
def answer(banana_list):
guards= [[] for i in range(len(banana_list))]
bad=0
for i in range(len(guards)):
for j in range(len(guards)):
if(loops(banana_list[i], banana_list[j])):
guards[i].append(j)
to_process=len(banana_list)
while(to_process>0):
# we first find the lesser used number
min_num=0
for i in range(len(guards)):
if(i!=0 and (len(guards[i])<len(guards[min_num]) or guards[min_num]
== [-1]) and guards[i]!=[-1]):
min_num=i
# if this node absolutely cannot be paired we purge it
if((len(guards[min_num])) == 0 or (len(guards[min_num])==1 and
guards[min_num][0] == guards[min_num]) and guards[min_num] !=
[-1]):
remove(guards, min_num)
to_process-=1
bad+=1
else:
# now we deduce the lesser used node associated to this number
min_node=guards[min_num][0]
for i in range(len(guards[min_num])):
if(i!=0 and guards[min_num][i]!=min_num and len(guards[guards[min_num][i]])<len(guards[min_node])):
min_node=guards[min_num][i]
# if we fail here infinite loop, which is bad because that means
# only processed nodes exist and we haven't exited; logic bug
if(guards[min_node]!=[-1]):
remove(guards, min_num)
remove(guards, min_node)
to_process-=2
return bad