Accenture Core Computer Science Core Computer Science Medium

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 a solution to fix it to the slowness?

Show answer & explanation

Answer: C. Although `rec(i)` always returns the same value, it recalculates from scratch every call. Memoize the result after first calculation and reuse it thereafter.

The function exhibits exponential time complexity O(3^n) due to overlapping subproblems—the same rec(i) is computed multiple times. For example, rec(3) calls rec(2), rec(1), and rec(0), but rec(2) independently recalculates rec(1) and rec(0) again. Memoization (caching results) eliminates redundant computations, reducing complexity to O(n). Options A and B are incorrect: the if statements are not the bottleneck, and integer overflow is not the issue since the problem uses multiple precision integers.

Step-by-step Derivation:
Time complexity analysis:

Without memoization: rec(n) calls rec(n-1) + rec(n-2) + rec(n-3), leading to ~3^n total function calls.
For n=4: rec(0) is called 7 times, rec(1) is called 6 times, rec(2) is called 3 times (redundant work).
For n=1000: Without memoization, this is infeasible; with memoization, O(n) time and O(n) space suffice.

Fixed approach using memoization:

memo = {}
function rec(i):
    if i in memo:
        return memo[i]
    if i == 0:
        return 1
    ans = 0
    if i >= 1:
        ans += rec(i-1)
    if i >= 2:
        ans += rec(i-2)
    if i >= 3:
        ans += rec(i-3)
    memo[i] = ans
    return ans

This reduces the time for n=1000 from infeasible to milliseconds.

There is a staircase of n steps and you are on the bottom of the staircase, on the 0-th step.

More Accenture technical mcq questions