I encountered the following algorithmic question which has strict constraints on runtime (<10s and no large memory footprint) and I am stumped. My approach fails half the test cases.

Question

A box contains a number of items that can only br removed 1 at a time or 3 at a time.

How many ways can the box be emptied? the answer can be very large so return it as modulo of 10^9 7.

for example,there are n=7 items initially.They can be removed nine ways,as follows:

1.(1,1,1,1,1,1,1)
2.(1.1.1.1.3)
3.(1,1,1,3,1)
4.(1,1,3,1,1)
5.(1,3,1,1,1)
6.(3,1,1,1,1)
7.(1,3,3)
8.(3,1,3)
9.(3,3,1)

So the function should return 9.

Function Description: Your function must take in a parameter, n for the number of items, and return an integer which denotes the number of ways to empty the box.

Constraints: 1<=n<=10^8

Sample cases :

Input: 1
Sample OutPut: 1
Explanation: There is only 1 way to remove 1 item. Answer=(100000007)=1

Input: 7
Sample OutPut: 9
There is only 9 ways to remove 7 items

My Approach

This leads to a standard recurrence relation where f(n) = f(n-3) f(n-1) for n > 2, so i did it as follows

def memoized_number_of_ways(dic, n):
    if n not in dic:
        dic[n] = memoized_number_of_ways(dic, n-3)   memoized_number_of_ways(dic, n-1)
    return dic[n]

def numberOfWays(n):
    # Write your code here
    memoize = {1:1,2:1,3:2}
    import math
    ans = memoized_number_of_ways(memoize,n)
    return ans % (math.pow(10,9)   7)

However this fails on any case where n > 10**2. How can you do this problem while accomodating n up to 10^8 and in less than 10s with not much memory?

CodePudding user response：

Just write your recurrence using matrices (pardon my way of writing matrices, StackOverflow doesn't allow LaTeX).

[f(n)  ] = [1 0 1] [f(n-1)  ]
[f(n-1)] = [1 0 0] [f(n-2)  ]
[f(n-2)] = [0 1 0] [f(n-3)  ]

Now all you have to do is raise a 3x3 matrix (modulo fixed constant) to power n (or n-3 or something like that, depending on your base column vector, fill in the details), and then multiply it by a "base case" column vector. This can be done in time O(logn).

PS: You may want to lookup matrix exponentiation.

CodePudding user response：

Your solution is on the right track and the bug is not related to your algorithm (Yay).

The problem is when you are performing operations on some big numbers you lose precision. Notice that you can apply the mod 10 ** 9 7 along your code since addition is not affected by it. By doing so you keep all your numbers below a certain size and you will not have any floating point precision errors:

import math

def memoized_number_of_ways(dic, n):
    if n not in dic:
        dic[n] = (memoized_number_of_ways(dic, n-3)   memoized_number_of_ways(dic, n-1)) % (math.pow(10,9)   7)
    return dic[n]

def numberOfWays(n):
    memoize = {1:1,2:1,3:2}
    ans = memoized_number_of_ways(memoize,n)
    return ans

Note that for you to be able to answer the question for n > 1000 you need to solve this recursion error problem.

Unfortunately even a very efficient solution (hint: you don't really need more than 3 items in your dict at any moment) will not solve the question for n ~ 10 ** 9 under a second. And you will need to find another way - a great option is the second answer here :)

CodePudding user response：

Here's a simple iterative O(n) time / O(1) space solution whose optimized version takes 6 seconds on a medium-fast machine (unoptimized takes 15 seconds there).

Unoptimized (Try it online!):

def solve(n):
    mod = 10**9   7
    a = b = c = 1
    for _ in range(n):
        a, b, c = b, c, (a c) % mod
    return a

print(solve(7))
print(solve(10**8))

Optimized (Try it online!):

def solve(n):
    mod = 10**9   7
    a = b = c = 1
    for _ in range(n // 300):
        for _ in range(100):
            a  = c
            b  = a
            c  = b
        a %= mod
        b %= mod
        c %= mod
    for _ in range(n % 300):
        a, b, c = b, c, (a c) % mod
    return a

CodePudding user response：

A matrix power solution like described by advocateofnone that takes about 1 millisecond (Try it online!):

import numpy as np
from time import time

class ModInt:
    def __init__(self, x):
        self.x = x % (10**9   7)
    def __add__(a, b):
        return ModInt(a.x   b.x)
    def __mul__(a, b):
        return ModInt(a.x * b.x)
    def __str__(self):
        return str(self.x)

def solve(n):
    O = ModInt(0)
    I = ModInt(1)
    A = np.matrix([[O,I,O], [O,O,I], [I,O,I]])
    return (A**n)[2,2]

for _ in range(3):
    t0 = time()
    print(solve(10**8), time() - t0)

Output (result and time in seconds for n=10⁸, three attempts):

109786077 0.0010712146759033203
109786077 0.0010180473327636719
109786077 0.0009677410125732422

Another, taking about 0.5 milliseconds (Try it online!):

import numpy as np
from time import time

def solve(n):
    A = np.matrix([[0,1,0], [0,0,1], [1,0,1]])
    power = 1
    mod = 10**9   7
    while n:
        if n % 2:
            power = power * A % mod
        A = A**2 % mod
        n //= 2
    return power[2,2]

for _ in range(3):
    t0 = time()
    print(solve(10**8), time() - t0)