GATE 2014 CS (CS3) – Question 47
To move from 0 to 100 on the number line, each step moves right one unit or uses a prespecified shortcut (i,j), i < j, directly from i to j. At most one shortcut involves any number, and 9 has a shortcut to 15. T(k) is the minimum steps from k to 100. If T(9) = 1 + min(T(y),T(z)), find yz.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 150 to 150
Explanation
At position9the next step either moves one unit to10or uses the shortcut to15. ThusT(9)=1+min(T(10),T(15)). The requested product is **10×15=150**. The recurrence compares remaining optimal costs after each permitted first step.