# Huge Fibonacci Number modulo m

This problem was taken from the *Coursera ***Data Structures and Algorithms Specialization**, specifically from the** ****Algorithmic Toolbox Course**, Week 2, that I’ve recently completed. If you are taking that course or plan to take that course, please **don’t look ahead** at the solution as it will be against the Honor Code and won’t do you any good.

#### Problem Introduction

The Fibonacci numbers are defined as follows: **F(0)** = **0**, **F(1)** = **1**, and **F(i)** = **F(i−1) + F(i−2)** for i ≥ 2.

#### Problem Description

**Task:** Given two integers **n** and **m**, output **F(n) mod m** (that is, the remainder of **F(n)** when **divided by m**).**Input Format:** The input consists of two integers **n** and **m** given on the same line (separated by a space).**Constraints:** 1 ≤ **n** ≤ 10^18 , 2 ≤ **m** ≤ 10^5 .**Output Format:** Output **F(n) mod m****Time Limits:** C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.**Memory Limit:** 512 Mb

#### Sample

**Input:**281621358815590 30524

**Output:**

11963

#### What To Do

In this problem, the given number **n** may be really huge. Hence an algorithm looping for **n** iterations will not fit into one second for sure. Therefore we need to avoid such a loop.

To get an idea how to solve this problem without going through all **F(i)** for **i** from *0 to n*, let’s see what happens when **m** is small — say, *m = 2* or *m = 3*.

Take a detailed look at this table. Do you see? Both these sequences are periodic! For *m = 2*, the period is *011* and has length *3*, while for *m = 3* the period is *01120221* and has length *8*. Therefore, to compute, say, **F(2015) mod 3** we just need to *find the remainder of 2015* when *divided by 8*. Since *2015 = 251·8+7*, we conclude that *F(2015) mod 3 = F 7 mod 3 = 1*.

This is true in general: for any integer *m ≥ 2*, the sequence **F(n) mod m** is periodic. The period always starts with *01* and is known as **Pisano period**.

### My Solution:

#### Explanation:

I couldn’t find a suitable definition for Pisano period so that I could make a naive algorithm. Well, it turns out, I was looking at the wrong place. The whole time, it was right in front of my eyes but I couldn’t see it. So, without further ado, here’s the definition. This was a very tricky one. I had to search a lot and read quite a few posts in the Course forum to understand the algorithm.

The algorithm to compute the get_fibonacci_huge was given in the What To Do section. “Therefore, to compute, say, **F(2015) mod 3** we just need to *find the remainder of 2015* when *divided by 8*. Since *2015 = 251·8+7*, we conclude that *F(2015) mod 3 = F 7 mod 3 = 1*.” We just have to generalize it.

First we need to find the *remainder of **F(n)** divided by the length of Paisano period given *** m**. To find the

*length of Paisano period for*

**, simply find the remainder of F(0) mod m to F(m*m) mod m and stop as soon as you encounter**

*m***01**, as they indicate that the next iteration is being started, and return the length up to that point.

Now, you only need to find the F(remainder), which is going to be a lot less than F(n) and simply return it.

**If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than w elcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.**