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.
 

44 lines
1.6 KiB

"""
Creating a perfect tree and going through it would be way over the top
for that, so we just do a recursive search calculating on the fly the values,
which results in an O(log(n)) complexity
"""
def find_item(item,cur,dif):
#the difference between the right node and the left
#node is the floor of the right node divided by 2: since we have a perfect
#tree our tree have the same number of nodes on the left side and right
#side; as such dividing by 2 should get you to the left one.
right_node=cur-1
left_node=right_node-dif//2
#Check readme.txt
if(right_node==item or left_node==item):
return cur
else:
#Cannot be on the right side, otherwise it'd be larger than the
#top left node thanks to perfect trees properties.
if(item<=left_node):
return find_item(item,left_node,dif//2)
else:
return find_item(item,right_node,dif//2)
#Check readme.txt for what this function does, almost no computation there
def answer(h, q):
#check readme.txt
if(h > 30 or h < 1):
raise ValueError('Height is outside of bounds')
if(len(q) > 10000 or len(q) < 1):
raise ValueError('Flux converters list is outside of bounds')
#Note: A perfect binary tree has 2n+1-1 nodes, where n is the height
#https://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html
items=(2**h)-1
array=[]
for i in range(len(q)):
if (q[i]<items and q[i]>0):
array.append(find_item(q[i],items,items-1))
else:
array.append(-1)
return array