Problem 10: A Weird Fruit You have a weird fruit with you that you can either sell as it is...
Texas Instruments technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Problem 10: A Weird Fruit**
You have a weird fruit with you that you can either sell as it is or you can divide it magically into 3 parts 1/2, 1/3, 1/4 and sell them. It is given that the division performed is an integer division and initially the weight of the fruit is n units.
You have to determine the maximum weight of the fruit that you can obtain from the magical division procedure. You are given the following pseudocode for performing this operation:
Solve(n):
if(n==0):
return 0
return X
Analyse the code and choose the correct option that fills the blank X.
Note:
- Example: n=2, if you divide it you will get 1,0,0 weights i.e 1 unit, so max is 2 unit of weight
- Example: n=12, if you divide it you will get 6,4,3 so total is 13 (you don't divide them further).
Show answer & explanation
The problem asks for the maximum weight obtainable by either keeping the fruit as is (weight n) or dividing it into three parts (n/2, n/3, n/4) and potentially dividing those parts further. This is a classic dynamic programming/recursion problem where the optimal value at state n is the maximum of the current value and the sum of the optimal values of its decomposed parts.
Step-by-step Derivation:
Step 1: Analyze the decision process. At any weight 'n', we have two choices:
- Choice 1: Sell the fruit as it is. The weight obtained is 'n'.
- Choice 2: Divide the fruit into three parts using integer division: floor(n/2), floor(n/3), and floor(n/4). Since each of these parts can also be further divided to potentially increase the total weight, we must recursively call the function for each part: solve(n/2) + solve(n/3) + solve(n/4).
Step 2: Formulate the recurrence relation. To maximize the weight, we take the maximum of these two choices:
MaxWeight(n) = max(n, MaxWeight(n/2) + MaxWeight(n/3) + MaxWeight(n/4)).
Step 3: Verify with provided examples.
- Example 1: n = 2.
solve(2) = max(2, solve(1) + solve(0) + solve(0)).
solve(1) = max(1, solve(0)+solve(0)+solve(0)) = 1.
solve(2) = max(2, 1 + 0 + 0) = 2. (Matches example). - Example 2: n = 12.
solve(12) = max(12, solve(6) + solve(4) + solve(3)).
solve(6) = max(6, solve(3)+solve(2)+solve(1)) = max(6, 3+2+1) = 6.
solve(4) = max(4, solve(2)+solve(1)+solve(1)) = max(4, 2+1+1) = 4.
solve(3) = max(3, solve(1)+solve(1)+solve(0)) = max(3, 1+1+0) = 3.
solve(12) = max(12, 6 + 4 + 3) = max(12, 13) = 13. (Matches example).
Step 4: Match the result to the options. Option A correctly implements this recursive logic.