There is a staircase of n steps and you are on the bottom of the staircase, on the 0-th step.
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
There is a staircase of n steps and you are on the bottom of the staircase, on the 0-th step. You can go up any of 1, 2, or 3 steps at a time. Let us consider the problem of counting the number of step-taking patterns that will put you on exactly the n-th step from the bottom.
For instance, if there are n = 4 steps, there are 7 patterns as follows. Each number is the number of steps you take at one time:
- 1, 1, 1, 1
- 2, 1, 1
- 1, 2, 1
- 1, 1, 2
- 2, 2
- 1, 3
- 3, 1
For this problem, you implemented a function solve as follows. Note that all the variables are multiple precision integers.
function rec(i):
if i == 0:
return 1
else:
ans = 0
if i >= 1:
ans += rec(i-1)
if i >= 2:
ans += rec(i-2)
if i >= 3:
ans += rec(i-3)
return ans
function solve(n):
return rec(n)
However, the program is too slow and it does not return the answer for n = 1000 even if you wait a whole day. You want to speed up the program so that it returns the answer in one second even if n is in the range between 1000 and 10000.
Which one of the following correctly states the reason the function is too slow and the solution to fix the slowness?
Show answer & explanation
The recursive function has exponential time complexity O(3^n) because it recalculates the same subproblems repeatedly. For example, rec(5) calls rec(4), rec(3), and rec(2); but rec(4) also calls rec(3) and rec(2), creating massive redundant computation. Memoization (storing computed results) reduces this to O(n) time complexity, enabling n=1000 to compute in seconds. Option A is incorrect because the number of if statements is not the bottleneck. Option B is wrong because the problem uses multiple precision integers to handle large numbers, and integer overflow isn't the issue—the problem is algorithmic, not computational limits.
Step-by-step Derivation:
Time complexity analysis: The recursive tree for rec(n) branches with degree 3 at each level. Without memoization, the same values like rec(1), rec(2) are computed thousands of times. For n=1000, the call tree has approximately 3^1000 nodes, which is astronomically large. With memoization, each rec(i) for i=0 to n is computed exactly once, giving O(n) time and O(n) space. For n=1000, this requires ~1000 computations instead of 3^1000, easily completing in under a second.