The Binary Tree Lineage

Easy
0/40
0 upvote
Asked in company
PhonePe

Problem statement

In a distant galaxy, a species' lineage is tracked using an infinite binary tree. The gender of each individual is determined by a simple set of genetic rules:

  • The ancestor at the root of the tree (level 1) is a Male ('M').
  • If a parent is a Male ('M'), their left child is a Male ('M') and their right child is a Female ('F').
  • If a parent is a Female ('F'), their left child is a Female ('F') and their right child is a Male ('M').


    You are given n (a level in the tree, 1-indexed) and k (a position within that level, 1-indexed from left to right). Your task is to determine the gender of the individual at that specific position.


    • Detailed explanation ( Input/output format, Notes, Images )
    Input Format: 
    A single line containing two space-separated integers, n and k.


    Output Format: 
    Print a single character, either 'M' or 'F', representing the gender of the individual at the specified location.


    Note: 
    Level n of the tree contains 2^(n-1) individuals.

Building the tree or the string for a large n is not feasible due to memory and time constraints. The solution must use the recursive structure of the problem to work backwards from the target position to the root.

The first half of any level is an exact copy of the previous level. The second half of any level is an inverted copy of the previous level (M becomes F, F becomes M).
    Sample Input 1:
    3 3


    Sample Output 1:
    F


    Explanation for Sample 1:
    The tree develops as follows:
- Level 1: M
- Level 2: M F (from the root 'M')
- Level 3: (M F) (F M) (from the nodes 'M' and 'F' at level 2)
The 3rd individual at level 3 is 'F'.


    Sample Input 2:
    1 1


    Sample Output 2:
    M


    Explanation for Sample 2:
    The individual at level 1, position 1 is the root, which is 'M'.


    Expected Time Complexity:
    The expected time complexity is O(n).


    Constraints:
    1 <= n <= 60
1 <= k <= 2^(n-1)

Time limit: 1 sec
    Approaches (1)
    The Binary Tree Lineage
    Time Complexity
    Space Complexity
    Code Solution
    (100% EXP penalty)
    The Binary Tree Lineage
    Full screen
    Console