 # GUESST04 - Editorial

Author: Vivek Kumar Mishra
Tester: Harshit Pandey
Editorialist: Harshit Sharma

EASY

Recursion

# PROBLEM:

Find the Kth fruit on Nth level

# QUICK EXPLANATION:

Use recursion to find the answer

# EXPLANATION:

Let us assume the structure to be a tree where the root node will be Apple.
We have to find Kth fruit on the Nth level. Now, if the Kth Fruit of the Nth level is the left child of its parent fruit, then it will be of the same type, else it will be of the opposite type. This can be done recursively.

# SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

string kthsol(int n, long long int k)
{
// Base Condition
if (n == 1 or k == 1)
{
return “A”;
}
long long int par = (k + 1) / 2;

``````string sol = kthsol(n - 1, par);

if (k == 2 * par - 1)
{
return sol;
}
else
{
if (sol == "A")
{
return "O";
}
else
{
return "A";
}
}
``````

}

void testcase()
{
int n, k;
cin >> n >> k;
cout << kthsol(n,k) << endl;
return;
}

int main()
{
int t;
cin >> t;
while(t–)
{
testcase();
}
}