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.

45 lines
1.6KB

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