#!/usr/bin/python2
# Ion Flux Relabeling
# ===================
# Oh no! Commander Lambda's latest experiment to improve the efficiency of her
# LAMBCHOP doomsday device has backfired spectacularly. She had been improving
# the structure of the ion flux converter tree, but something went terribly
# wrong and the flux chains exploded. Some of the ion flux converters survived
# the explosion intact, but others had their position labels blasted off. She's
# having her henchmen rebuild the ion flux converter tree by hand, but you
# think you can do it much more quickly - quickly enough, perhaps, to earn a
# promotion!
# Flux chains require perfect binary trees, so Lambda's design arranged the ion
# flux converters to form one. To label them, she performed a post-order
# traversal of the tree of converters and labeled each converter with the order
# of that converter in the traversal, starting at 1. For example, a tree of 7
# converters would look like the following:
# 7
# 3 6
# 1 2 4 5
# Write a function solution(h, q) - where h is the height of the perfect tree
# of converters and q is a list of positive integers representing different
# flux converters - which returns a list of integers p where each element in p
# is the label of the converter that sits on top of the respective converter in
# q, or -1 if there is no such converter. For example, solution(3, [1, 4, 7])
# would return the converters above the converters at indexes 1, 4, and 7 in a
# perfect binary tree of height 3, which is [3, 6, -1].
# The domain of the integer h is 1 <= h <= 30, where h = 1 represents a perfect
# binary tree containing only the root, h = 2 represents a perfect binary tree
# with the root and two leaf nodes, h = 3 represents a perfect binary tree with
# the root, two internal nodes and four leaf nodes (like the example above),
# and so forth. The lists q and p contain at least one but no more than 10000
# distinct integers, all of which will be between 1 and 2^h-1, inclusive.
def findParent(h, n):
start = 1
end = 2**h - 1
if end == n:
return -1
while(True):
end = end - 1
mid = start + (end - start)//2
if mid == n or end == n:
return end + 1
elif n < mid:
end = mid
else:
start = mid
def solution(h, q):
p = []
for i in q:
p.append(findParent(h, i))
return p
print(solution(5, [19, 14, 28])) # 21,15,29
print(solution(3, [7, 3, 5, 1])) # -1,7,6,3
