0

I've got the following question on a job interview:

"A box contain a number of chocolates that can only be removed 1 at a time or 3 at a time. How many ways can the box be emptied?"

At first, I tried to do it with recursion, and it worked. This is the following python code:

def numberOfWays(n):
    if n <= 2:
        return 1
    else:
        return numberOfWays(n - 3) + numberOfWays(n - 1)

However, the website didn't allow the use of recursion. I've tried it many times, but I just couldn't turn it into an iterative function, since on the original function, I have to output two results.

Improve this question
2
  • You're supposed to understand what it's actually doing and turn it into a simple statement. Commented Jan 19, 2022 at 18:11
  • 2
    "the website didn't allow the use of recursion" -- did you get a "time limit exceeded" message? If not, how do you know it didn't allow recursion? The problem might be the efficiency rather than the recursion, per se -- you could memoize the function or maybe use math to solve it without enumerating the ways recursively. Commented Jan 19, 2022 at 18:19

2 Answers 2

Reset to default
1

This problem is very similar to Fibonacci and you can create an iterative solutions that is much more performant than the recursive solution. I modified the recursive function a little bit because from reading the question I interpret n = 0 as having 0 ways to empty the box by removing 1 or 3 items. Here is the modified recursive function.

def numberOfWays(n):
if n <= 0:
    return 0
elif n in (2, 1):
    return 1
elif n == 3:
    return 2
else:
    return numberOfWays(n - 3) + numberOfWays(n - 1)

Here is an iterative solution that will use less memory than the one Michael provided since it only stores 3 numbers instead of every single number in the series up to n:

def numberOfWays(n):
if n == 0:
    return 0
elif n <= 2:
    return 1
elif n == 3:
    return 2
a, b, c, = 1, 1, 2
for i in range(n-3):
    a, b, c, = b, c, c + a

return c

I counted the number of loop iterations for the iterative function and the number of function calls for the recursive one to show how much better it performs.

Iterative
n of 10 = 28 | Loop Iterations: 7
n of 9 = 19 | Loop Iterations: 6
n of 8 = 13 | Loop Iterations: 5
n of 7 = 9 | Loop Iterations: 4
n of 6 = 6 | Loop Iterations: 3
n of 5 = 4 | Loop Iterations: 2
n of 4 = 3 | Loop Iterations: 1
n of 3 = 2 | Loop Iterations: 0
n of 2 = 1 | Loop Iterations: 0
n of 1 = 1 | Loop Iterations: 0
n of 0 = 0 | Loop Iterations: 0

Recursive:
n of 10 = 28 | Function calls: 37
n of 9 = 19 | Function calls: 25
n of 8 = 13 | Function calls: 17
n of 7 = 9 | Function calls: 11
n of 6 = 6 | Function calls: 7
n of 5 = 4 | Function calls: 5
n of 4 = 3 | Function calls: 3
n of 3 = 2 | Function calls: 1
n of 2 = 1 | Function calls: 1
n of 1 = 1 | Function calls: 1
n of 0 = 0 | Function calls: 1

Caching/Memoizing the result would be good if this function were used in software where it will be called many times with the same parameters regardless of the underlying implementation. However this probably won't help you pass all the automated tests in an online coding challenge.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I also thought about turning the recursive function into a tail function, storing the 3 values would ease the memory.
1

Translating your recursive algorithm into a naive iterative solution will still have runtime complexity of O(2^n).

def NoW_iter(n):
    if n <= 2: return 1
    c = 2
    l = [n-3, n-1]
    while l:
        i = l.pop()
        if i > 2:
            c += 1
            l += [i-3, i-1]
    return c

An easy way to fix runtime issues for your algorithm would be to memoize interim results

from functools import lru_cache

@lru_cache(maxsize=None)
def numberOfWays(n):
    if n <= 2:
        return 1
    else:
        return numberOfWays(n - 3) + numberOfWays(n - 1)

This can be done in an iterative approach as well with a runtime complexity of O(n).

def NoW_memo(n):
    d = {0: 1, 1: 1, 2: 1}
    for i in range(3, n+1):
        d[i] = d[i-3] + d[i-1]
    return d[n]
Improve this answer

4 Comments

Is there any way to lower the complexity?
@Eduardo - The third approach is O(n) vs O(2^n) for the other solutions (solution 2 is still faster for small n). The third approach is one of the simplest examples of dynamic programming. I updated the answer.
Thank you very much.
Solution 2 is O(2*n)-ish (I think) which is O(n) as well.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.