is there a way to optimise this simple multiplication algorithm?

Question

while doing a local coding contest i found a problem that was simple yet difficult to optimize, the problem was as follows: "given an array of [1, 2, 3], find i-th number using this formula: arr[i] = arr[i - 3] + arr[i - 2] * arr[i - 1], and type the value of arr[249] % 169 into the answer box."

it wasn't too difficult, but since the formula used the last 3 numbers in the array, that means that the it was VERY exponential, the difference between arr[8] and arr[9] was in the trillions, and it gets way bigger way faster.

the problem in the contest was seemingly asking for a lot, but i do have some suspicion that the modulus part of it could've heavily simplified the process. how? i really don't know.

i tried both a simple recursive function and a for loop in python (i am not experienced with any other language, so i cant try this in a faster one), neither of those approaches could brute force this problem in an acceptable amount of time, i didn't try to exploit the modulus part because i don't know how i can achieve that, nor am i sure if it is even possible.

here are my solutions, in function form:

def recursion(n):
    if n <= 3:
        return n
    
    return recursion(n - 3) + recursion(n - 2) * recursion(n - 1)
 
def forLoop(n):
    arr = []
    for i in range(n):
        if len(arr) < 3:
            arr.append(i + 1)
            continue
        
        arr.append(arr[0] + arr[1] * arr[2])
        arr.pop(0)
    
    return arr[2]
 
 
testNum = 6
r = recursion(testNum)
f = forLoop(testNum)
 
print(r, f)

Answer 1

There are two problems in your approach:

1. The problem can be solved in linear time, instead of recursion, using a simple for loop.
2. We can use the Modulo Arithmetic rules to keep the numbers always in [0, 169).

Solving the first problem

We can use the memoization here. Suppose that we want to find arr[100]. What information do we need to find this?

We have the formula: arr[i] = arr[i - 3] + arr[i - 2] * arr[i - 1]

Therefore, we will have arr[100] = arr[97] + arr[98] * arr[99].

Think about the following scenario: We have arr[0], arr[1], arr[2]. What if we compute and store arr[3]? What if after storing arr[3], we compute arr[4]? ...? What if after storing arr[99], we compute arr[100]?

We can easily see that arr[100] can be computed in constant time, as we already have arr[97], arr[98] and arr[99] stored with us.

You can see another example of this approach here: nth Fibonacci number in linear time.

Solving the second problem

Coming to second problem, the problem can be solved using the rules of Modulo Arithmetic. Here are the rules that we need:

(a + b) % n = ((a % n) + (b % n)) % n
(a * b) % n = ((a % n) * (b % n)) % n

Since we only require arr[249] % 169, we can assume n=169 and our problem is reduced to finding arr[i] % n for all i from 0 to 249. Thus, we can convert our equation into this:

Let b[i] = arr[i] % n. We need b[249].

b[i]
= arr[i] % n
= (arr[i - 3] + arr[i - 2] * arr[i - 1]) % n
= ((arr[i - 3] % n) + (arr[i - 2] * arr[i - 1]) % n) % n
= (b[i - 3] + ((arr[i - 2] % n) * (arr[i - 1] % n)) % n) % n
= (b[i - 3] + (b[i - 2] * b[i - 1]) % n) % n.

Therefore, instead of returning arr[249] % 169, we simply return b[249].

Pseudo code

Here is the pseudo code for the same:

mod = 169
b = [0,0,0,...] # Size of b is 250
b[0] = 1
b[1] = 2
b[2] = 3

for i = 3 to 249 (included):
    b[i] = (b[i - 3] + (b[i - 2] * b[i - 1]) % mod) % mod

print b[249]

This should make everything clear.