A Geometric series is a series with a constant ratio between successive terms. The first term of the series is denoted by a and the common ratio is denoted by r. The series looks like this:-
The task is to find the sum of such a series, mod M.
Examples:
Input: a = 1, r = 2, N = 10000, M = 10000 Output: 8751 Input: a = 1, r = 4, N = 10000, M = 100000 Output: 12501
Approach:
- To find the sum of series
we can easily take a as common and find the sum of
and multiply it with a.
- Steps to find the sum of the above series.
- Here, it can be resolved that:
- Here, it can be resolved that:
If we denote,
then,
and,
This will work as our recursive case.
- So, the base cases are:
Sum(r, 0) = 1. Sum(r, 1) = 1 + r.
Below is the implementation of the above approach.
C++
// C++ implementation to // illustrate the program #include <iostream>using namespace std;// Function to calculate the sum // recursively int SumGPUtil(long long int r, long long int n, long long int m){ // Base cases if (n == 0) return 1; if (n == 1) return (1 + r) % m; long long int ans; // If n is odd if (n % 2 == 1) { ans = (1 + r) * SumGPUtil((r * r) % m, (n - 1) / 2, m); } else { // If n is even ans = 1 + (r * (1 + r) * SumGPUtil((r * r) % m, (n / 2) - 1, m)); } return (ans % m);}// Function to print the long value of Sum void SumGP(long long int a, long long int r, long long int N, long long int M){ long long int answer; answer = a * SumGPUtil(r, N, M); answer = answer % M; cout << answer << endl; }// Driver Code int main(){ // First element long long int a = 1; // Common difference long long int r = 4; // Number of elements long long int N = 10000; // Mod value long long int M = 100000; SumGP(a, r, N, M); return 0;}// This code is contributed by sanjoy_62 |
Java
// Java implementation to // illustrate the program import java.io.*;class GFG{// Function to calculate the sum // recursively static long SumGPUtil(long r, long n, long m){ // Base cases if (n == 0) return 1; if (n == 1) return (1 + r) % m; long ans; // If n is odd if (n % 2 == 1) { ans = (1 + r) * SumGPUtil((r * r) % m, (n - 1) / 2, m); } else { // If n is even ans = 1 + (r * (1 + r) * SumGPUtil((r * r) % m, (n / 2) - 1, m)); } return (ans % m);}// Function to print the value of Sum static void SumGP(long a, long r, long N, long M) { long answer; answer = a * SumGPUtil(r, N, M); answer = answer % M; System.out.println(answer); }// Driver Code public static void main (String[] args){ // First element long a = 1; // Common difference long r = 4; // Number of elements long N = 10000; // Mod value long M = 100000; SumGP(a, r, N, M);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 implementation to illustrate the program # Function to calculate the sum # recursivelydef SumGPUtil (r, n, m): # Base cases if n == 0: return 1 if n == 1: return (1 + r) % m # If n is odd if n % 2 == 1: ans = (1 + r) * SumGPUtil(r * r % m, (n - 1)//2, m) else: #If n is even ans = 1 + r * (1 + r) * SumGPUtil(r * r % m, n//2 - 1, m) return ans % m# Function to print the value of Sumdef SumGP (a, r, N, M): answer = a * SumGPUtil(r, N, M) answer = answer % M print(answer)#Driver Programif __name__== '__main__': a = 1 # first element r = 4 # common difference N = 10000 # Number of elements M = 100000 # Mod value SumGP(a, r, N, M) |
C#
// C# implementation to // illustrate the program using System;class GFG{// Function to calculate the sum // recursively static long SumGPUtil(long r, long n, long m){ // Base cases if (n == 0) return 1; if (n == 1) return (1 + r) % m; long ans; // If n is odd if (n % 2 == 1) { ans = (1 + r) * SumGPUtil((r * r) % m, (n - 1) / 2, m); } else { // If n is even ans = 1 + (r * (1 + r) * SumGPUtil((r * r) % m, (n / 2) - 1, m)); } return (ans % m);}// Function to print the value of Sum static void SumGP(long a, long r, long N, long M){ long answer; answer = a * SumGPUtil(r, N, M); answer = answer % M; Console.WriteLine(answer); }// Driver Code public static void Main() { // First element long a = 1; // Common difference long r = 4; // Number of elements long N = 10000; // Mod value long M = 100000; SumGP(a, r, N, M);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript implementation to // illustrate the program// Function to calculate the sum // recursively function SumGPUtil(r, n, m){ // Base cases if (n == 0) return 1; if (n == 1) return (1 + r) % m; let ans; // If n is odd if (n % 2 == 1) { ans = (1 + r) * SumGPUtil((r * r) % m, (n - 1) / 2, m); } else { // If n is even ans = 1 + (r * (1 + r) * SumGPUtil((r * r) % m, (n / 2) - 1, m)); } return (ans % m);} // Function to print the value of Sum function SumGP(a, r, N, M) { let answer; answer = a * SumGPUtil(r, N, M); answer = answer % M; document.write(answer); } // Driver Code // First element let a = 1; // Common difference let r = 4; // Number of elements let N = 10000; // Mod value let M = 100000; SumGP(a, r, N, M); </script> |
12501
Time complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
