Problem Statement There is a staircase of n steps and you are on the bottom of the...
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Problem Statement
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 provided function exhibits exponential time complexity due to overlapping subproblems—the same values of rec(i) are computed multiple times across different recursive branches. For example, rec(2) is computed multiple times when computing rec(4). This causes the time complexity to grow exponentially (approximately O(3^n)), making it infeasible for n = 1000. Memoization (caching computed values) transforms this into O(n) time complexity. Option C correctly identifies this redundant computation and proposes caching as the solution. Options A and B are incorrect: replacing if statements with a for loop does not reduce redundant calls, and integer overflow is not the issue since multiple precision integers handle arbitrarily large numbers.
Step-by-step Derivation:
Time complexity analysis of the naive recursive solution:
- rec(n) calls rec(n-1), rec(n-2), and rec(n-3)
- Each of those calls rec three more times
- This creates a call tree with approximately 3^n nodes
- For n = 1000, this is computationally infeasible
With memoization:
- Each unique subproblem rec(i) is solved exactly once and stored
- Subsequent calls to rec(i) return the cached result in O(1)
- Total time complexity becomes O(n) with O(n) space
- For n = 1000, this executes in milliseconds
Example trace for n = 4 (naive):
- rec(4) → calls rec(3), rec(2), rec(1)
- rec(3) → calls rec(2), rec(1), rec(0) [rec(2) computed again]
- rec(2) → calls rec(1), rec(0) [rec(1) computed again]
- rec(1) → calls rec(0) [rec(0) computed again]
- rec(0) → returns 1
Notice rec(2) is computed at least twice, rec(1) at least three times, and rec(0) multiple times. This redundancy explodes exponentially for larger n.