Family Structure

Easy
0/40
Average time to solve is 10m
profile
Contributed by
116 upvotes
Asked in companies
OptumAmazonD.E.Shaw

Problem statement

Aakash is a member of Ninja club. He has a weird family structure. Every male member (M) gives birth to a male child first and then a female child, whereas every female (F) member gives birth to a female child first and then to a male child. Aakash analyses this pattern and wants to know what will be the Kth child in his Nth generation. Can you help him?

A sample generation tree is shown, where ‘M’ denotes the male member and ‘F’ denotes the female member.

Note 
The generation tree starts with a male member i.e. Aakash. 
Every member has exactly two children. 
The given N and K will always be valid.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases. Then the test cases follow.
The first and the only line of each test case contains two space-separated integers ‘N’ and ‘K’ denoting the generation number and position of the child in Nth generation, respectively.

Output Format

For each test case, print the gender of the Kth child in the Nth generation. If the gender is male, print “Male” else print “Female” (without quotes). 
The output of each test case is printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 50
1 <= K <= 2^(N - 1)
where ‘T’ is the number of test cases, ‘N’ is generation number and ‘K’ is the position of the child in the Nth generation.

Sample Input 1:

2
2 2 
3 4

Sample Output 1:

Female
Male

Explanation for Sample Input 1:

Test Case 1:  2nd child of the 2nd generation is shown in green colour. 


Test Case 2:  4th child of the 3rd generation is shown in green colour.

Sample Input 2:

3
5 1 
3 1
4 4

Sample Output 2:

Male
Male
Male
Hint

Try to find a recursive based on the relation between generation number and position of the child in Nth generation.

Approaches (1)
Recursion

The idea is to find the gender of the parent of the Kth child in Nth generation. Now, if the Kth child of the Nth generation is the first child of its parent, then it’s gender will be the same as the parent’s gender else it will be the opposite. This can be done recursively. 
 

Algorithm: 

  • The idea is to use recursion.
  • Base condition, If 'N' or 'K' is 1, return “Male”, as the first child of every generation is male.
  • Find the parent of the Kth child of Nth generation. It will be floor((K + 1) / 2). Store it in a variable “par”.
  • Note that the generation of the parent is “N - 1”. Thus, the parent will be the floor((K + 1) / 2)th child of (N - 1)th generation.
  • Recursively find the gender of the parent and store it in a string "parGender". If the Kth child of Nth generation is the first child of its parent, i.e. if 'K' is equal to (2 * par - 1), return the gender of the parent ("genParent").
  • Else, return the gender opposite of its parent’s gender. If its parent is “Male”, return “Female” else return “Male”.

 

For example: N = 3, K = 3 

 

We need to find the gender of the 3rd child in the 3rd generation. 

Now, par = (K + 1) / 2 = (3 + 1) / 2 and generation = N - 1 = 2. 

Now, we have to find the parent of the second child of the second generation. 

par = (2 + 1) / 2 = 1 and generation = 1. 

As the generation is 1, simply return “Male”. 

Now, we know the gender of the parent of the 2nd child of the 2nd generation. As the 2nd child of the 2nd generation is the second child of its parent, its gender will be Female(opposite of the parent). 

Now, we know the gender of the parent of the 3rd child of the 3rd generation. As the 3rd child of the 3rd generation is the first child of its parent, its gender will be Female( same as the parent’s). 

Thus, “Female” is the required answer. 

Time Complexity

O(min(N, log(K)), where N is the number of generations and K is the position of the child in the Nth generation. 

We are doing a constant amount of work in each recursive call and there will be at-most min(N, log(K)) recursive calls. Thus, the final time complexity is O(N). 

Space Complexity

O(N), where N is the number of generations. 

We are calling the same recursive function (N - 1) times. Thus, recursion stack space is required of the size (N - 1). Hence, the space complexity is O(N). 

Code Solution
(100% EXP penalty)
Family Structure
Full screen
Console