Find last two digits of Nth Fibonacci number

Problem

perm_identityUser Actions

Given an integer n (possibly very large), return the last two digits of the n-th Fibonacci number F(n).

• Input: integer n (may be provided as an integer or as a decimal string).
• Output: F(n) mod 100 (two least-significant decimal digits).

Examples

Example 1

Input: n = 65
Output: 65

Example 2

Input: n = 365
Output: 65

Solution

Observations: the sequence F(i) mod 100 is periodic (Pisano period). For modulus 100 the period divides 100*100=10000; in practice the period for modulus 100 is 300. That means F(n) mod 100 = F(n % 300) mod 100. We present three methods:

Method 1 — Naive Fibonacci

Intuition

Compute F(n) directly and take F(n) % 100. This is simple but infeasible when n is very large because Fibonacci numbers grow exponentially.

Approach

• Iterate the recurrence F(0)=0, F(1)=1, updating a,b = b, a+b until index n, then return F(n) % 100.

Code

C++

class Solution {
 public:
  long long fib_naive(unsigned long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    long long a = 0, b = 1;
    for (unsigned long long i = 2; i <= n; ++i) { long long nxt = a + b; a = b; b = nxt; }
    return b % 100;
  }
};

Complexity

• ⏰ Time complexity: O(n) — iterates n steps.
• 🧺 Space complexity: O(1) extra space.

Method 2 — Iterative modulo 100

Intuition

We only need the last two digits, so perform all arithmetic modulo 100 to keep values small.

Approach

• Maintain a = 0, b = 1 and iterate n times updating a, b = b, (a+b) % 100.

Edge cases:

• If n == 0 return 0.

Code

C++

class SolutionMod100 {
 public:
  int last_two(unsigned long long n) {
    int a = 0, b = 1;
    if (n == 0) return 0;
    for (unsigned long long i = 1; i <= n; ++i) { int nxt = (a + b) % 100; a = b; b = nxt; }
    return a % 100;
  }
};

Go

package main

func LastTwoFib(n uint64) int {
  a, b := 0, 1
  if n == 0 { return 0 }
  for i := uint64(1); i <= n; i++ { a, b = b, (a+b) % 100 }
  return a % 100
}

Java

class Solution {
  public int lastTwo(long n) {
    int a = 0, b = 1;
    if (n == 0) return 0;
    for (long i = 1; i <= n; ++i) { int nxt = (a + b) % 100; a = b; b = nxt; }
    return a % 100;
  }
}

Kotlin

class Solution {
  fun lastTwo(n: Long): Int {
    var a = 0; var b = 1
    if (n == 0L) return 0
    for (i in 1..n) { val nxt = (a + b) % 100; a = b; b = nxt }
    return a % 100
  }
}

Python

class Solution:
    def last_two(self, n: int) -> int:
        a, b = 0, 1
        if n == 0:
            return 0
        for _ in range(1, n + 1):
            a, b = b, (a + b) % 100
        return a % 100

    def last_two_str(self, s: str) -> int:
        # reduce large decimal string n modulo 300 (Pisano period)
        r = 0
        for ch in s:
            r = (r*10 + (ord(ch) - 48)) % 300
        return self.last_two(r)

Rust

pub struct Solution;
impl Solution {
  pub fn last_two(mut n: u128) -> u8 {
    if n == 0 { return 0 }
    let (mut a, mut b) = (0u8, 1u8);
    for _ in 1..=n { let nxt = ((a as u16 + b as u16) % 100) as u8; a = b; b = nxt; }
    a
  }
}

Complexity

• ⏰ Time complexity: O(n) — linear iterations.
• 🧺 Space complexity: O(1).

Method 3 — Pisano-cycle reduction (period 300)

Intuition

The sequence F(i) mod 100 repeats with period 300. Therefore F(n) mod 100 = F(n % 300) mod 100. Compute idx = n % 300 (stream digits if n is a string) and then compute F(idx) mod 100.

Approach

1. Precompute cycle[0..299] with cycle[i] = F(i) mod 100.
2. Compute idx = n % 300 (if n is a decimal string compute idx by streaming digits: idx = (idx*10 + d) % 300).
3. Return cycle[idx].

Edge cases: n == 0 -> 0.

Code

C++

class SolutionPisano300 {
 public:
  int last_two(unsigned long long n) {
    static int cycle[300]; static bool init = false;
    if (!init) { init = true; cycle[0]=0; cycle[1]=1; for (int i=2;i<300;++i) cycle[i] = (cycle[i-1]+cycle[i-2])%100; }
    return cycle[n % 300];
  }
};

Go

package main

var pisano300 = func() [300]int {
  var c [300]int
  c[0], c[1] = 0, 1
  for i := 2; i < 300; i++ { c[i] = (c[i-1] + c[i-2]) % 100 }
  return c
}()

func LastTwoFibPisano(n uint64) int { return pisano300[n % 300] }

Java

class Solution {
  private static final int[] CYCLE = new int[300];
  static { CYCLE[0]=0; CYCLE[1]=1; for (int i=2;i<300;++i) CYCLE[i]=(CYCLE[i-1]+CYCLE[i-2])%100; }

  public int lastTwo(long n) { return CYCLE[(int)(n % 300)]; }
}

Kotlin

object Solution {
  private val CYCLE = IntArray(300).also { it[0]=0; it[1]=1; for (i in 2 until 300) it[i]=(it[i-1]+it[i-2])%100 }
  fun lastTwo(n: Long) = CYCLE[(n % 300).toInt()]
}

Python

class Solution:
    CYCLE = [0,1] + [0]*298
    for i in range(2,300):
        CYCLE[i] = (CYCLE[i-1] + CYCLE[i-2]) % 100

    def last_two(self, n: int) -> int:
        return Solution.CYCLE[n % 300]

    def last_two_str(self, s: str) -> int:
        r = 0
        for ch in s:
            r = (r*10 + (ord(ch)-48)) % 300
        return Solution.CYCLE[r]

Rust

pub struct Solution;
impl Solution {
  fn pisano300() -> [u8;300] {
    let mut c = [0u8;300]; c[0]=0; c[1]=1;
    for i in 2..300 { c[i] = ((c[i-1] as u16 + c[i-2] as u16) % 100) as u8 }
    c
  }

  pub fn last_two(n: u128) -> u8 { let c = Self::pisano300(); c[(n % 300) as usize] }
}

Complexity

• ⏰ Time complexity: O(1) per query after precomputation (precompute cost O(300) negligible). If using iterative method, O(n).
• 🧺 Space complexity: O(1) extra space (300-entry cycle is constant-size).