Finding Profession

Intuition

The organization forms a perfect binary tree: level 1 starts with an Engineer at position 1. Each node has a left and right child whose professions follow fixed inheritance rules, but when a parent sits at an even position those left/right roles swap. Instead of simulating the entire tree down to the target level, walk upward from the given position and track how many right-child steps flip the starting profession.

Algorithm

1Initialize flip = 0 (starting profession at position 1 is Engineer).
2While pos > 1:
3 If pos is even, set flip = 1 - flip (right child toggles profession).
4 Move to parent with pos = (pos + 1) / 2.
5If flip is 0, return "Engineer"; otherwise return "Doctor".

Example Walkthrough

Input: level = 3, pos = 5

1.Start at pos = 5 (odd): no flip, parent = (5 + 1) / 2 = 3.
2.At pos = 3 (odd): no flip, parent = 2.
3.At pos = 2 (even): flip becomes 1, parent = 1.
4.Reached root; one toggle from Engineer gives Doctor.

Output: Doctor

Common Pitfalls

•Only even positions (right children) toggle flip while climbing upward.
•Parent index is (pos + 1) / 2, not pos / 2.
•Do not build the full tree level by level; the upward walk is O(log level).

Finding Profession.java

Java

// Approach: Walk from the target position up to the root. Each even position means the node is a
// right child, which toggles inherited profession relative to the parent; odd positions preserve it.
// Time: O(log level) Space: O(1)

class Solution {

    public String profession(int level, int pos) {
        int flip = 0;
        while (pos > 1) {
            if (pos % 2 == 0) {
                flip = 1 - flip;
            }
            pos = (pos + 1) / 2;
        }

        if (flip == 0) {
            return "Engineer"; 
        }else {
            return "Doctor";
        }
    }
}

Was this solution helpful?