A algorithm problem of complete two binary tree

Question

A complete binary tree with a maximum depth of 16 is known, with all leaf nodes having the same depth. If a small ball is placed at the root node, the ball will begin to fall along the root node. There is a switch on each node in the complete binary tree. The default is all off. When the ball falls, the state of the switch changes whenever a ball falls on a switch. When the ball reaches a node, if the switch on the node is closed, go to the left to go to the ball, otherwise go to the right until it reaches the leaf node. Please help me find the leaf node number after the 12345th ball fell.

Answer 1

You can simulate the given problem and notice that the leaf node at which the ball ends tends to repeat itself after a point of time. For example, for a binary tree of depth 3, the leaf nodes at which the ball ends for multiple roll of the balls are 1 3 2 4 1 3 2 4 1 3 2 4 . . . (assuming the leaf nodes are numbered starting from 1). As visible, the sequence of length 2^3-1 = 4 keeps repeating itself. We can store this sequence in an array and answer the query for any n^th ball throw by looking up the entry corresponding to the n mod 2^depth-1 index in this array.

Since our depth is upto 16, the total number of operations required to generate the recurring sequence is 2^16-1 * 16 = 524288 operations.

Sharing the code for the same https://ideone.com/uuNV2g

#include <iostream>
#include <map>
#include <vector>
using namespace std;

map<int, bool> states; // default value is False
int MAX_DEPTH = 16;

int dfs(int cur, int depth = 0) {
    if(depth == MAX_DEPTH) {
        return cur - (1<<MAX_DEPTH) + 1;
    }

    if(states[cur] == 0) {
        states[cur] = !states[cur];
        return dfs(2*cur, depth+1);
    }
    else {
        states[cur] = !states[cur];
        return dfs(2*cur+1, depth+1);
    }

}

int main() {
    int until = (1LL<<(MAX_DEPTH-1));
    vector<int> pos; // 0 indexed
    for(int i = 1; i <= until; i++) {
        // cout << dfs(1) << ' ';
        pos.push_back(dfs(1));
    }

    cout << pos[(12344%until)]; 
    // 12344 instead of 12345 since the sequence is 0 indexed
}

Hope it works out.