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.
#Check readme.txt
if(right_node==item or left_node==item):
return cur
#Cannot be on the right side, otherwise it'd be larger than the
#top left node thanks to perfect trees properties.
return find_item(item,left_node,dif//2)
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
for i in range(len(q)):
if (q[i]<items and q[i]>0):
return array