First term from given Nth term of the equation F(N) = (2 * F(N – 1)) % 10^9 + 7
Given an integer N and an integer FN which denotes the Nth term of the linear equation F(N) = (2 * F(N – 1)) % M, where M is 109 + 7, the task is to find the value of F(1).
Examples:
Input : N = 2, FN = 6
Output:3
Explanation:
If F(1) = 3, F(2) = (2 * F(1)) % M = (2 * 3) % M = 6.
For F(1) = 3 the given linear equation satisfies the value of F(2).
Therefore, the value of F(1) is 3.Input : N = 3, FN = 6
Output: 500000005
Explanation:
If F(1) = 500000005
F(2) = (2 * 500000005) % M = 3
F(3) = (2 * 3) % M = 6
For F(1) = 500000005 the given linear equation satisfies the value of F(3).
Therefore, the value of F(1) is 500000005
Naive Approach: The simplest approach to solve this problem is to try all possible values of F(1) in the range [1, M – 1] and check if any value satisfies the given linear equation or not. If found to be true, then print the value of F(1).
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is based on the following observations:
Given the linear equation, F(N) = 2 * F(N – 1) ——(1)
put the value of F(N – 1) = 2 * F(N – 2) in equation(1)
=>F(N) = 2 * (2 * F(N – 2)) ——–(2)
put the value of F(N – 2) = 2 * F(N – 3) in equation(2)
=>F(N) = 2* (2 * (2 * F(N – 3)))
…………………………….
…………………………….
=>F(N) = 2(N – 1) F(N – (N – 1)) = 2(N – 1) F(1)
=>F(1) = F(N) / 2(N – 1)
Follow the steps below to solve the problem:
- Calculate the modulo multiplicative inverse of 2(N – 1) under modulo M, say modInv.
- Finally, print the value of F(N) * modInv.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define M 1000000007 // Function to find the value // of power(X, N) % M long long power( long long x, long long N) { // Stores the value // of (X ^ N) % M long long res = 1; // Calculate the value of // power(x, N) % M while (N > 0) { // If N is odd if (N & 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res; } // Function to find modulo multiplicative // inverse of X under modulo M long long moduloInverse( long long X) { return power(X, M - 2); } // Function to find the value of F(1) long long F_1( long long N, long long F_N) { // Stores power(2, N - 1) long long P_2 = power(2, N - 1); // Stores modulo multiplicative // inverse of P_2 under modulo M long long modInv = moduloInverse(P_2); // Stores the value of F(1) long long res; // Update res res = ((modInv % M) * (F_N % M)) % M; return res; } // Driver code int main() { long long N = 3; long long F_N = 6; cout << F_1(N, F_N); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ static final int M = 1000000007 ; // Function to find the // value of power(X, N) % M static long power( long x, long N) { // Stores the value // of (X ^ N) % M long res = 1 ; // Calculate the value // of power(x, N) % M while (N > 0 ) { // If N is odd if (N % 2 == 1 ) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1 ; } return res; } // Function to find modulo // multiplicative inverse // of X under modulo M static long moduloInverse( long X) { return power(X, M - 2 ); } // Function to find the // value of F(1) static long F_1( long N, long F_N) { // Stores power(2, N - 1) long P_2 = power( 2 , N - 1 ); // Stores modulo multiplicative // inverse of P_2 under modulo M long modInv = moduloInverse(P_2); // Stores the value of F(1) long res; // Update res res = ((modInv % M) * (F_N % M)) % M; return res; } // Driver code public static void main(String[] args) { long N = 3 ; long F_N = 6 ; System.out.print(F_1(N, F_N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement # the above approach M = 1000000007 # Function to find the value # of power(X, N) % M def power(x, N): # Stores the value # of (X ^ N) % M res = 1 # Calculate the value of # power(x, N) % M while (N > 0 ): # If N is odd if (N & 1 ): # Update res res = (res * x) % M # Update x x = (x * x) % M # Update N N = N >> 1 return res # Function to find modulo multiplicative # inverse of X under modulo M def moduloInverse(X): return power(X, M - 2 ) #Function to find the value of F(1) def F_1(N, F_N): # Stores power(2, N - 1) P_2 = power( 2 , N - 1 ) # Stores modulo multiplicative # inverse of P_2 under modulo M modInv = moduloInverse(P_2) # Stores the value of F(1) res = 0 # Update res res = ((modInv % M) * (F_N % M)) % M return res # Driver code if __name__ = = '__main__' : N = 3 F_N = 6 print (F_1(N, F_N)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ static readonly int M = 1000000007; // Function to find the // value of power(X, N) % M static long power( long x, long N) { // Stores the value // of (X ^ N) % M long res = 1; // Calculate the value // of power(x, N) % M while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res; } // Function to find modulo // multiplicative inverse // of X under modulo M static long moduloInverse( long X) { return power(X, M - 2); } // Function to find the // value of F(1) static long F_1( long N, long F_N) { // Stores power(2, N - 1) long P_2 = power(2, N - 1); // Stores modulo multiplicative // inverse of P_2 under modulo M long modInv = moduloInverse(P_2); // Stores the value of F(1) long res; // Update res res = ((modInv % M) * (F_N % M)) % M; return res; } // Driver code public static void Main(String[] args) { long N = 3; long F_N = 6; Console.Write(F_1(N, F_N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to implement // the above approach var M = 100000007; // Function to find the // value of power(X, N) % M function power(x, N) { // Stores the value // of (X ^ N) % M var res = 1; // Calculate the value // of power(x, N) % M while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x) % M; } // Update x x = (x * x) % M; // Update N N = N >> 1; } return res; } // Function to find modulo // multiplicative inverse // of X under modulo M function moduloInverse( X) { return power(X, M - 2); } // Function to find the // value of F(1) function F_1( N, F_N) { // Stores power(2, N - 1) var P_2 = power(2, N - 1); // Stores modulo multiplicative // inverse of P_2 under modulo M var modInv = moduloInverse(P_2); // Stores the value of F(1) var res; // Update res res = ((modInv % M) * (F_N % M)) % M; return res; } // Driver code var N = 3; var F_N = 6; document.write(F_1(N, F_N)); // This code is contributed by shivanisinghss2110 </script> |
500000005
Time Complexity: O(log2N) since in the power function in every call the value of n is divided by 2 until it reaches 1 thus the algorithm takes logarithmic time to execute.
Auxiliary Space: O(1) since no extra array is used so the space taken by the algorithm is constant
Contact Us