I do not understand what is wrong with my code. I have been at this for the past 5 days and I am approaching the final day until I can no longer submit. First here is the problem:

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 following:

      7
    /   \
  3      6
 /  \   / \
1   2  4   5

Write a function answer(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, answer(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.

Here is my solution :

#root: root
#result: list that tracks the history of the nodes along the path
#parent: list of the parent node(s)
#subt: what ill be subtracting from the node if I go left
#cnode: current node
#part: partition that separates whether the node goes left or right on the tree
#_r: resets the values at the beginning of each cycle 



def solution(h, q):
    root = 1
    result = []
    parent = []
    
    # This give the root Value of the Binary tree
    for i in range(1,h):
        root = (root*2) 1
        subt = root
    
    subt = (subt   1)/2
    cnode = root
    part = ((cnode - 1)/2) 1
    
    cnode_r = cnode
    part_r = part
    subt_r = subt
    
    result.append(cnode)
    
    for x in q:
        cnode = cnode_r
        part = part_r 
        subt = subt_r
        flag = True
        if x == root:
            parent.append(-1)
        else:
            while flag:
                if x == cnode:
                    flag = False
                elif x < part:
                    cnode = cnode - subt
                    subt = subt/2
                    part = (cnode - subt)   1
                    result.append(cnode)
                elif x >= part:
                    cnode = cnode-1
                    subt = subt/2
                    part = (cnode - subt)   1
                    result.append(cnode)
            if x == cnode:
                parent.append(result[-2])
    parent = [int(x) for x in parent]
    return parent

I have passed the public test cases but it fails the hidden test. All of my manual attempts to look for a bug have led me nowhere. I am guessing I have done something fundamentally wrong, but I cannot pinpoint it. Here are the test cases:

Test cases

Inputs:

(int) h = 3
(int list) q = [7, 3, 5, 1]

Output:

(int list) [-1, 7, 6, 3]

Inputs:

(int) h = 5

(int list) q = [19, 14, 28]

Output:

(int list) [21, 15, 29]

Any help or direction would be greatly appreciated!

CodePudding user response：

The problem is that the outer loop doesn't reset the result list to its initial value, and so the result for a given x depend on what happened in previous iterations.

For example your code will have the following output:

print(solution(2, [2]))  # [3]

This is correct, but then when we add a value in the second argument...

print(solution(2, [1, 2]))  # [3, 1]

...the solution for 2 is no longer correct. The output should have been [3, 3].

To resolve this, move these two lines...

result = []
result.append(cnode)

...into the loop, just before the if. Now your code will work.