CODEWITHSUNDEEP
algorithmformularecurrence
User_Targaryen
User_Targaryen

Reputation: 4225

General formula for a recurrence relation?

I was solving a coding question, and found out the following relation to find the number of possible arrangements:

one[1] = two[1] = three[1] = 1

one[i] = two[i-1] + three[i-1]

two[i] = one[i-1] + three[i-1]

three[i] = one[i-1] + two[i-1] + three[i-1]

I could have easily used a for loop to find out the values of the individual arrays till n, but the value of n is of the order 10^9, and I won't be able to iterate from 1 to such a huge number.

For every value of n, I need to output the value of (one[n] + two[n] + three[n]) % 10^9+7 in O(1) time.

Some results:

I was not able to find out a general formula for n for the above after spending hours on it. Can someone help me out.

Edit: 

n = 1, result(1) = 3
n = 2, result(2) = 7
n = 3, result(3) = result(2)*2 + result(1) = 17
n = 4, result(4) = result(3)*2 + result(2) = 41

So, result(n) = result(n-1)*2 + result(n-2) OR T(n) = 2T(n-1) + T(n-2)

Upvotes: 0

Views: 104

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58221

You can use a matrix to represent the recurrence relation. (I've renamed one, two, three to a, b, c).

(a[n+1]) = ( 0 1 1 ) (a[n])
(b[n+1])   ( 1 0 1 ) (b[n])
(c[n+1])   ( 1 1 1 ) (c[n])

With this representation, it's feasible to compute values for large n, by matrix exponentation (modulo your large number), using exponentation by squaring. That'll give you the result in O(log n) time.

(a[n]) = ( 0 1 1 )^(n-1) (1)
(b[n])   ( 1 0 1 )       (1)
(c[n])   ( 1 1 1 )       (1)

Here's some Python that implements this all from scratch:

# compute a*b mod K where a and b are square matrices of the same size
def mmul(a, b, K):
    n = len(a)
    return [
        [sum(a[i][k] * b[k][j] for k in xrange(n)) % K for j in xrange(n)]
        for i in xrange(n)]

# compute a^n mod K where a is a square matrix
def mpow(a, n, K):
    if n == 0: return [[i == j for i in xrange(len(a))] for j in xrange(len(a))]
    if n % 2: return mmul(mpow(a, n-1, K), a, K)
    a2 = mpow(a, n//2, K)
    return mmul(a2, a2, K)

M = [[0, 1, 1], [1, 0, 1], [1, 1, 1]]

def f(n):
    K = 10**9+7
    return sum(sum(a) for a in mpow(M, n-1, K)) % K

print f(1), f(2), f(3), f(4)
print f(10 ** 9)

Output:

3 7 17 41
999999966

It runs effectively instantly, even for the n=10**9 case.

Upvotes: 2

Related Questions