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:
![[1 + r + r^2 + r^3 + . . . + r^(2*n+1)] = (1+r)*(1 + (r^2) + (r^2)^2 + (r^2)^3 + . . . + (r^2)^n)](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20968%2032'%3E%3C/svg%3E "Rendered by QuickLaTeX.com")
- 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> |
Output:
12501
Time complexity: O(log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
