`"""` `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]0):` ` array.append(find_item(q[i],items,items-1))` ` else:` ` array.append(-1)` ``` return array ```