I'm doing some an Algorithm Design online course as a way of learning algorithmis and Python as well. One of these challenges requires that I write code for finding a "Huge Fibonacci Number Modulo m". The code works, but for some inputs (such as 99999999999999999 100000), it exceeds the alloted time limit. However, I can't see a way of improving performance.

Here is the Problem Description:

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

Here is the code:

As a complete Python and algorithms newbie, any input is appreciated. Thanks in advance for the help!

I'm doing some an Algorithm Design online course as a way of learning algorithms and Python as well. One of these challenges requires that I write code for finding a "Huge Fibonacci Number Modulo m". The code works, but for some inputs (such as 99999999999999999 100000), it exceeds the allocated time limit. However, I can't see a way of improving performance.

Here is the problem description:

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

Here is the code:

As a complete Python and algorithms newbie, any input is appreciated.

Here is the Problem Description:

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

I'm doing some an Algorithm Design online course as a way of learning algorithmis and Python as well. One of these challenges requires that I write code for finding a "Huge Fibonacci Number Modulo m". The code works, but for some inputs (such as 99999999999999999 100000), it exceeds the alloted time limit. However, I can't see a way of improving performance.

Here is the code:

#!/usr/bin/python3
from sys import stdin 
def get_fibonacci_huge(n, m):
 fibonacciNumbers = [0, 1, 1]
 pisanoNumbers = [0, 1, 1]
 pisanoPeriod = 3
 
 for i in range(2, n):
 if pisanoNumbers[i - 1] == 0 and pisanoNumbers[i] == 1:
 pisanoPeriod = i - 1
 break;
 
 nextFibonacci = fibonacciNumbers[i - 1] + fibonacciNumbers[i];
 
 fibonacciNumbers.append(nextFibonacci)
 pisanoNumbers.append(nextFibonacci % m)
 else:
 pisanoPeriod = None # If we exhausted all values up to n, then the pisano period could not be determined. 
 
 if pisanoPeriod is None:
 return pisanoNumbers[n]
 else:
 return pisanoNumbers[n % pisanoPeriod]
if __name__ == '__main__':
 dataEntry = stdin.readline()
 n, m = map(int, dataEntry.split())
 print(get_fibonacci_huge(n, m))

For the an input of 99999999999999999 100000, it takes around 5.10 seconds, and the maximum allowed time is 5.00 seconds.

As a complete Python and algorithms newbie, any input is appreciated. Thanks in advance for the help!

I'm doing some an Algorithm Design online course as a way of learning algorithmis and Python as well. One of these challenges requires that I write code for finding a "Huge Fibonacci Number Modulo m". The code works, but for some inputs (such as 99999999999999999 100000), it exceeds the alloted time limit. However, I can't see a way of improving performance.

Here is the code:

#!/usr/bin/python3
from sys import stdin 
def get_fibonacci_huge(n, m):
 fibonacciNumbers = [0, 1, 1]
 pisanoNumbers = [0, 1, 1]
 pisanoPeriod = 3
 
 for i in range(2, n):
 if pisanoNumbers[i - 1] == 0 and pisanoNumbers[i] == 1:
 pisanoPeriod = i - 1
 break;
 
 nextFibonacci = fibonacciNumbers[i - 1] + fibonacciNumbers[i];
 
 fibonacciNumbers.append(nextFibonacci)
 pisanoNumbers.append(nextFibonacci % m)
 else:
 pisanoPeriod = None # If we exhausted all values up to n, then the pisano period could not be determined. 
 
 if pisanoPeriod is None:
 return pisanoNumbers[n]
 else:
 return pisanoNumbers[n % pisanoPeriod]
if __name__ == '__main__':
 dataEntry = stdin.readline()
 n, m = map(int, dataEntry.split())
 print(get_fibonacci_huge(n, m))

For an input of 99999999999999999 100000, it takes around 5.10 seconds, and the maximum allowed time is 5.00 seconds.

As a complete Python and algorithms newbie, any input is appreciated. Thanks in advance for the help!