Problem

Compute the Fibonacci number F(n) modulo m, where n may be extremely large and m is small (for example m < 1000).

  • Input: integers n and m (note: n can be given as a large integer or as a decimal string).
  • Output: F(n) mod m.

Examples

Example 1

1
2
3

Input: n = 2015, m = 3
Output: 1
Explanation: Pisano period for m=3 is 8, 2015 % 8 = 7, and F(7) % 3 = 1

Example 2

1
2
3

Input: n = 10, m = 2
Output: 1
Explanation: sequence of F(i) mod 2 is periodic with period 3; F(10) mod 2 = 1

The key observation: the sequence F(i) mod m is periodic for any integer m >= 2. The period (Pisano period) always starts with 0, 1. If we can find the Pisano period P(m), then F(n) mod m = F(n mod P(m)) mod m, so we only need to compute Fibonacci for a much smaller index.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Fi 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
Fi mod 2 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
Fi mod 3 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1

Solution

Two practical methods are common for computing F(n) mod m when n is huge:

  • Method 1 — Pisano-period detection + iterative Fibonacci (simple, works when m is small).
  • Method 2 — Pisano-reduction + fast-doubling Fibonacci (asymptotically faster for large reduced indices).

Method 1 — Pisano-period detection + iterative Fibonacci

Intuition

The sequence F(i) mod m repeats with period P(m) (Pisano period). Detecting P lets us replace n by r = n % P, drastically reducing work.

Approach

  • Compute P by iterating F(i) mod m starting from (0,1) and stop when the pair (prev, cur) becomes (0, 1) again; P is the number of steps to that repeat.
  • If n is too large to fit in native types (given as a decimal string), compute r = n % P by processing digits: r = (r*10 + d) % P for each digit d.
  • Compute F(r) mod m by iterating r times (since r < P and P ≤ m*m, this is feasible for small m).

Edge cases:

  • If m == 1, return 0.
  • If n == 0, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
 public:
  static int pisano_period(int m) {
    int prev = 0, cur = 1;
    for (int i = 0; i < m * m + 1; ++i) {
      int next = (prev + cur) % m;
      prev = cur; cur = next;
      if (prev == 0 && cur == 1) return i + 1;
    }
    return m * m;
  }

  long long get_fibonacci_huge(unsigned long long n, int m) {
    if (m == 1) return 0;
    int p = pisano_period(m);
    unsigned long long r = n % p;
    long long a = 0, b = 1;
    if (r == 0) return 0;
    for (unsigned long long i = 1; i <= r; ++i) {
      long long nxt = (a + b) % m;
      a = b; b = nxt;
    }
    return a % m;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

package main

func pisanoPeriod(m int) int {
  prev, cur := 0, 1
  for i := 0; i < m*m+1; i++ {
    next := (prev + cur) % m
    prev, cur = cur, next
    if prev == 0 && cur == 1 { return i + 1 }
  }
  return m*m
}

func GetFibonacciHuge(n uint64, m int) int {
  if m == 1 { return 0 }
  p := pisanoPeriod(m)
  r := n % uint64(p)
  a, b := 0, 1
  if r == 0 { return 0 }
  for i := uint64(1); i <= r; i++ {
    a, b = b, (a+b)%m
  }
  return a % m
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
  private static int pisanoPeriod(int m) {
    int prev = 0, cur = 1;
    for (int i = 0; i < m * m + 1; ++i) {
      int next = (prev + cur) % m; prev = cur; cur = next;
      if (prev == 0 && cur == 1) return i + 1;
    }
    return m * m;
  }

  public long getFibonacciHuge(long n, int m) {
    if (m == 1) return 0;
    int p = pisanoPeriod(m);
    long r = n % p;
    long a = 0, b = 1;
    if (r == 0) return 0;
    for (long i = 1; i <= r; ++i) {
      long nxt = (a + b) % m; a = b; b = nxt;
    }
    return a % m;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
  private fun pisanoPeriod(m: Int): Int {
    var prev = 0; var cur = 1
    for (i in 0..(m*m)) {
      val next = (prev + cur) % m
      prev = cur; cur = next
      if (prev == 0 && cur == 1) return i + 1
    }
    return m*m
  }

  fun getFibonacciHuge(n: Long, m: Int): Int {
    if (m == 1) return 0
    val p = pisanoPeriod(m)
    val r = (n % p).toInt()
    if (r == 0) return 0
    var a = 0; var b = 1
    for (i in 1..r) {
      val nxt = (a + b) % m
      a = b; b = nxt
    }
    return a % m
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def pisano_period(self, m: int) -> int:
        prev, cur = 0, 1
        for i in range(0, m * m + 1):
            prev, cur = cur, (prev + cur) % m
            if prev == 0 and cur == 1:
                return i + 1
        return m * m

    def get_fibonacci_huge(self, n: int, m: int) -> int:
        if m == 1:
            return 0
        p = self.pisano_period(m)
        r = n % p
        a, b = 0, 1
        if r == 0:
            return 0
        for _ in range(1, r + 1):
            a, b = b, (a + b) % m
        return a % m

    def str_mod(self, s: str, mod: int) -> int:
        r = 0
        for ch in s:
            r = (r * 10 + (ord(ch) - ord('0'))) % mod
        return r
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

pub struct Solution;
impl Solution {
  pub fn pisano_period(m: usize) -> usize {
    let (mut prev, mut cur) = (0usize, 1usize);
    for i in 0..(m*m+1) {
      let next = (prev + cur) % m;
      prev = cur; cur = next;
      if prev == 0 && cur == 1 { return i + 1 }
    }
    m*m
  }

  pub fn get_fibonacci_huge(mut n: u128, m: usize) -> usize {
    if m == 1 { return 0 }
    let p = Self::pisano_period(m);
    let r = (n % (p as u128)) as usize;
    if r == 0 { return 0 }
    let (mut a, mut b) = (0usize, 1usize);
    for _ in 1..=r {
      let nxt = (a + b) % m; a = b; b = nxt;
    }
    a % m
  }
}

Complexity

  • ⏰ Time complexity: O(m^2 + P) where P = P(m) ≤ m^2; detecting Pisano period takes up to O(m^2) steps and computing F(r) takes O(P) in the worst case. For small m (e.g., m < 1000) this is acceptable.
  • 🧺 Space complexity: O(1) extra space (only a few integer variables).

Method 2 — Pisano-reduction + fast-doubling Fibonacci

Intuition

After reducing n modulo the Pisano period P, computing F(r) can be done faster using the fast-doubling method in O(log r) time. Combining both steps yields O(m^2 + log P) time.

Approach

  • Find P = P(m) as in Method 1.
  • Compute r = n % P. If n is very large and given as a string, compute r digit-by-digit.
  • Use fast-doubling to compute F(r) mod m in O(log r) arithmetic steps.

Edge cases: same as Method 1.

Code (fast-doubling helper + usage)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class SolutionFD {
 public:
  // returns pair (F(n), F(n+1)) modulo m
  static std::pair<long long,long long> fib_pair(unsigned long long n, int m) {
    if (n == 0) return {0, 1};
    auto p = fib_pair(n >> 1, m);
    long long a = p.first; long long b = p.second;
    long long c = (a * ((2*b - a + m) % m)) % m; // F(2k)
    long long d = ( (a*a)%m + (b*b)%m ) % m;    // F(2k+1)
    if ((n & 1) == 0) return {c, d};
    else return {d, (c + d) % m};
  }
};
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def fib_pair(n: int, m: int) -> tuple:
    if n == 0:
        return (0, 1)
    a, b = fib_pair(n >> 1, m)
    c = (a * ((2*b - a) % m)) % m
    d = ((a*a) % m + (b*b) % m) % m
    if n & 1:
        return (d, (c + d) % m)
    else:
        return (c, d)

def get_fib_fast(n: int, m: int) -> int:
    return fib_pair(n, m)[0]

Complexity

  • ⏰ Time complexity: O(m^2 + log P); Pisano detection costs O(m^2) and fast-doubling costs O(log P) arithmetic operations.
  • 🧺 Space complexity: O(log P) recursion depth for the doubling recursion (or O(1) if implemented iteratively).

Notes

  • P(m) (Pisano period) satisfies P(m) ≤ m^2 so the detection step is bounded by m^2 iterations.
  • If n is supplied as a decimal string (too large to fit in integers), compute n % P by streaming digits: r = (r*10 + digit) % P.
  • For very large m, other techniques may be required.