Last digit of sum of numbers in the given range in the Fibonacci series
Given two non-negative integers M, N which signifies the range [M, N] where M ? N, the task is to find the last digit of the sum of FM + FM+1… + FN where FK is the Kth Fibonacci number in the Fibonacci series.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Examples:
Input: M = 3, N = 9
Output: 6
Explanation:
We need to find F3 + F4 + F5 + F6 + F7 + F8 + F9
=> 2 + 3 + 5 + 8 + 13 + 21 + 34 = 86.
Clearly, the last digit of the sum is 6.Input: M = 3, N = 7
Output: 1
Explanation:
We need to find F3 + F4 + F5 + F6 + F7
=> 2 + 3 + 5 + 8 + 13 = 31.
Clearly, the last digit of the sum is 1.
Naive Approach: The naive approach for this problem is to one by one find the sum of all Kth Fibonacci Numbers where K lies in the range [M, N] and return the last digit of the sum in the end. The time complexity for this approach is O(N) and this method fails for higher-ordered values of N.
Efficient approach:
C++
#include <bits/stdc++.h> using namespace std; long long getFibonacciPartialSumFast( long long m, long long n) { long long sum = 0; m = m % 60; n = n % 60; if (n < m) n += 60; long long current = 0; long long next = 1; for ( int i = 0; i <= n; i++) { if (i >= m) { sum += current; } long long newCurrent = next; next = next + current; current = newCurrent; } return sum % 10; } int main() { long long m = 2; long long n = 10; cout << getFibonacciPartialSumFast(m, n) << endl; return 0; } |
Java
import java.util.*; public class FibonacciPartialSum { private static long getFibonacciPartialSumFast( long m, long n) { long sum = 0 ; // The input arguments, as the last digit // pattern repeats with a period of 60, and the sum // of 60 such consecutive numbers is 0 mod 10 m = ( int )(m % 60 ); n = ( int )(n % 60 ); // Make sure n is greater than m if (n < m) n += 60 ; long current = 0 ; long next = 1 ; for ( int i = 0 ; i <= n; ++i) { if (i >= m) { sum += current; } long newCurrent = next; next = next + current; current = newCurrent; } return ( int )(sum % 10 ); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); long m = 2 ; long n = 10 ; System.out.println( getFibonacciPartialSumFast(m, n)); } } |
Python3
def getFibonacciPartialSumFast(m, n): sum = 0 # The input arguments, as the last digit # pattern repeats with a period of 60, and the sum # of 60 such consecutive numbers is 0 mod 10 m = m % 60 n = n % 60 # Make sure n is greater than m if n < m: n + = 60 current = 0 next = 1 for i in range (n + 1 ): if i > = m: sum + = current new_current = next next = next + current current = new_current return sum % 10 if __name__ = = "__main__" : m = 2 n = 10 print (getFibonacciPartialSumFast(m, n)) |
C#
using System; using System.Linq; using System.Collections.Generic; class GFG { static long getFibonacciPartialSumFast( long m, long n) { long sum = 0; // The input arguments, as the last digit // pattern repeats with a period of 60, and the sum // of 60 such consecutive numbers is 0 mod 10 m = m % 60; n = n % 60; // Make sure n is greater than m if (n < m) n += 60; long current = 0; long next = 1; for ( int i = 0; i <= n; i++) { if (i >= m) { sum += current; } long newCurrent = next; next = next + current; current = newCurrent; } return sum % 10; } static public void Main() { long m = 2; long n = 10; Console.Write(getFibonacciPartialSumFast(m, n)); } } // This code is contributed by ratiagrawal. |
Javascript
function getFibonacciPartialSumFast(m, n) { let sum = 0; m = m % 60; n = n % 60; if (n < m) n += 60; let current = 0; let next = 1; for (let i = 0; i <= n; i++) { if (i >= m) { sum += current; } let newCurrent = next; next = next + current; current = newCurrent; } return sum % 10; } let m = 2; let n = 10; console.log(getFibonacciPartialSumFast(m, n)); // This code is contributed by poojaagarwal2. |
2
Contact Us