Given a Geometric Progression series in arr[] and Q queries in the form of [L, R], where L is the left boundary of the range and R is the right boundary. The task is to find the sum of the Geometric Progression elements in the given range.
Note: The range is 1-indexed and1 ? L, R ? N, where N is the size of arr.
Examples:
Input: arr[] = {2, 4, 8, 16, 32, 64, 128, 256}, Q = [[2, 4], [2, 6], [5, 8]]
Output:
28
124
480
Explanation:
Range 1: arr = {4, 8, 16}. Therefore sum = 28
Range 2: arr = {4, 8, 16, 32, 64}. Therefore sum = 124
Range 3: arr = {32, 64, 128, 256}. Therefore sum = 480Input: arr[] = {7, 7, 7, 7, 7, 7}, Q = [[1, 6], [2, 4], [3, 3]]
Output:
42
21
7
Explanation:
Range 1: arr = {7, 7, 7, 7, 7, 7}. Therefore sum = 42
Range 2: arr = {7, 7, 7}. Therefore sum = 21
Range 3: arr = {7}. Therefore sum = 7
Approach: Since the given sequence is an Geometric progression, the sum can be easily found out in two steps efficiently:
- Get the first element of the range.
- If d = 1, then multiply d*k to it, else multiply the (dk – 1)/(d – 1) to it, where d is the common ratio of the GP and k is number of elements in the range.
For example:
Suppose a[i] be the first element of the range, d be the common ratio of GP and k be the number of elements in the given range.
Then the sum of the range would be
= a[i] + a[i+1] + a[i+2] + ….. + a[i+k-1]
= a[i] + (a[i] * d) + (a[i] * d * d) + …. + (a[i] * dk)
= a[i] * (1 + d + … + dk)
= a[i] * (dk – 1)/(d – 1)
Below is the implementation of the above approach:
C++
// C++ program to find the sum // of elements of an GP in the // given range#include <bits/stdc++.h>using namespace std;// Function to find sum in the given range int findSum(int arr[], int n, int left, int right) { // Find the value of k int k = right - left + 1; // Find the common difference int d = arr[1] / arr[0]; // Find the sum int ans = arr[left - 1]; if (d == 1) ans = ans * d * k; else ans = ans * ((int)pow(d, k) - 1 / (d - 1)); return ans; } // Driver Codeint main(){ int arr[] = { 2, 4, 8, 16, 32, 64, 128, 256 }; int queries = 3; int q[][2] = { { 2, 4 }, { 2, 6 }, { 5, 8 } }; int n = sizeof(arr) / sizeof(arr[0]); for(int i = 0; i < queries; i++) cout << (findSum(arr, n, q[i][0], q[i][1])) << endl; return 0;}// This code is contributed by divyeshrabadiya07 |
Java
// Java program to find the sum // of elements of an GP in the // given range import java.io.*; import java.util.*; class GFG{ // Function to find sum in the given range static int findSum(int[] arr, int n, int left, int right) { // Find the value of k int k = right - left + 1; // Find the common difference int d = arr[1] / arr[0]; // Find the sum int ans = arr[left - 1]; if (d == 1) ans = ans * d * k; else ans = ans * ((int)Math.pow(d, k) - 1 / (d - 1)); return ans; } // Driver Code public static void main(String args[]) { int[] arr = { 2, 4, 8, 16, 32, 64, 128, 256 }; int queries = 3; int[][] q = { { 2, 4 }, { 2, 6 }, { 5, 8 } }; int n = arr.length; for(int i = 0; i < queries; i++) System.out.println(findSum(arr, n, q[i][0], q[i][1])); } } // This code is contributed by offbeat |
Python3
# Python3 program to # find the sum of elements # of an GP in the given range # Function to find sum in the given range def findSum(arr, n, left, right): # Find the value of k k = right - left + 1 # Find the common difference d = arr[1] // arr[0] # Find the sum ans = arr[left - 1] if d == 1: ans = ans * d * k else: ans = ans * (d ** k - 1) // (d -1) return ans # Driver code if __name__ == '__main__': arr = [ 2, 4, 8, 16, 32, 64, 128, 256 ] queries = 3 q = [[ 2, 4 ], [ 2, 6 ], [ 5, 8 ]] n = len(arr) for i in range(queries): print(findSum(arr, n, q[i][0], q[i][1])) |
C#
// C# program to find the sum// of elements of an GP in the // given range using System; class GFG{ // Function to find sum in the given range static int findSum(int[] arr, int n, int left, int right){ // Find the value of k int k = right - left + 1; // Find the common difference int d = arr[1] / arr[0]; // Find the sum int ans = arr[left - 1]; if (d == 1) ans = ans * d * k; else ans = ans * ((int)Math.Pow(d, k) - 1 / (d - 1)); return ans;}// Driver Code public static void Main(string []args) { int[] arr = { 2, 4, 8, 16, 32, 64, 128, 256 }; int queries = 3; int[,] q = { { 2, 4 }, { 2, 6 }, { 5, 8 } }; int n = arr.Length; for(int i = 0; i < queries; i++) Console.Write(findSum(arr, n, q[i, 0], q[i, 1]) + "\n");} } // This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program to find the sum// of elements of an GP in the// given range// Function to find sum in the given rangefunction findSum(arr, n, left, right) { // Find the value of k let k = right - left + 1; // Find the common difference let d = arr[1] / arr[0]; // Find the sum let ans = arr[left - 1]; if (d == 1) ans = ans * d * k; else ans = ans * (Math.pow(d, k) - 1 / (d - 1)); return ans;}// Driver Codelet arr = [2, 4, 8, 16, 32, 64, 128, 256];let queries = 3;let q = [[2, 4], [2, 6],[5, 8]];let n = arr.length;for (let i = 0; i < queries; i++) document.write(findSum(arr, n, q[i][0], q[i][1]));// This code is contributed by blalverma92</script> |
28 124 480
- Time complexity: O(Q)
- Space complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
