3d challenge

1 files changed, 66 insertions, 0 deletions

diff --git a/2.2.py b/2.2.py
new file mode 100644
index 0000000..08a46c7
--- /dev/null
+++ b/2.2.py
@@ -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