A Flight of Stairs - Amazon Top Interview Questions

                        Solution in C++ :

const int mod = 1e9 + 7;

struct mtx {
    long long int a, b, c, d;
    mtx(long long int w, long long int x, long long int y, long long int z)
        : a(w), b(x), c(y), d(z) {
    }
    mtx operator*(mtx& other) {
        mtx A(a * other.a + b * other.c, a * other.b + b * other.d, c * other.a + d * other.c,
              c * other.b + d * other.d);
        A.a %= mod;
        A.b %= mod;
        A.c %= mod;
        A.d %= mod;
        return A;
    }
};

mtx power(mtx A, long long int k) {
    mtx B(1, 0, 0, 1);
    while (k) {
        if (k & 1) {
            B = B * A;
        }
        A = A * A;
        k /= 2;
    }
    return B;
}

int solve(int n) {
    mtx A(1, 1, 1, 0);
    mtx B = power(A, n);
    // cout << B.a << " " << B.b << endl << B.c << " " << B.d << endl;
    return B.a;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int n) {
        int a = 1;
        int b = 1;
        int c;
        for (int i = 2; i <= n; i++) {
            c = a;
            a = b;
            b = (b + c) % 1000000007;
        }
        return b;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, n):
        MOD = 10 ** 9 + 7

        def fib():
            a = b = 1
            yield a
            yield b
            while True:
                yield (a + b) % MOD
                a, b = b, (a + b) % MOD

        f = fib()
        for _ in range(n):
            next(f)
        return next(f)