diff options
Diffstat (limited to '2.2.py')
| -rw-r--r-- | 2.2.py | 66 |
1 files changed, 66 insertions, 0 deletions
@@ -0,0 +1,66 @@ +#!/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 |