Given an arithmetic 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 AP elements in the given range.
Note: The range is 1-indexed and 1 ? L, R ? N, where N is the size of arr.
Examples:
Input: arr[] = {2, 4, 6, 8, 10, 12, 14, 16}, Q = [[2, 4], [2, 6], [5, 8]]
Output:
18
40
52
Explanation:
Range 1: arr = {4, 6, 8}. Therefore sum = 18
Range 2: arr = {4, 6, 8, 10, 12}. Therefore sum = 40
Range 3: arr = {10, 12, 14, 16}. Therefore sum = 52Input: arr[] = {7, 14, 21, 28, 35, 42}, Q = [[1, 6], [2, 4], [3, 3]]
Output:
147
63
21
Explanation:
Range 1: arr = {7, 14, 21, 28, 35, 42}. Therefore sum = 147
Range 2: arr = {14, 21, 28}. Therefore sum = 63
Range 3: arr = {21}. Therefore sum = 21
Approach: Since the given sequence is an arithmetic progression, the sum can be easily found in two steps efficiently:
- Multiply the first element of the range by the number of elements in the range.
- Add (d*k*(k+1))/2 to it, where d is the common difference of the AP and k is (number of elements in the range – 1) which corresponds to the number of gaps.
For example:
Suppose a[i] be the first element of the range, d is the common difference of AP and k+1 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]
= a[i] + a[i] + d + a[i] + 2 * d + …. + a[i] + k * d
= a[i] * (k + 1) + d * (1 + 2 + … + k)
= a[i] * (k + 1) + (d * k * (k+1))/2
Below is the implementation of the above approach:
CPP
// C++ program to find the sum of elements// of an AP in the given range#include <bits/stdc++.h>using namespace std;// Function to find sum in the given rangeint findSum(int* arr, int n, int left, int right){ // Find the value of k int k = right - left; // Find the common difference int d = arr[1] - arr[0]; // Find the sum int ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans;}// Driver codeint main(){ int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16 }; int queries = 3; int q[queries][2] = { { 2, 4 }, { 2, 6 }, { 5, 6 } }; 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;} |
Java
// Java program to find the sum of elements// of an AP in the given rangeclass GFG{ // Function to find sum in the given rangestatic int findSum(int []arr, int n, int left, int right){ // Find the value of k int k = right - left; // Find the common difference int d = arr[1] - arr[0]; // Find the sum int ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans;} // Driver codepublic static void main(String[] args){ int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16 }; int queries = 3; int q[][] = { { 2, 4 }, { 2, 6 }, { 5, 6 } }; int n = arr.length; for (int i = 0; i < queries; i++) System.out.print(findSum(arr, n, q[i][0], q[i][1]) +"\n");}}// This code is contributed by Princi Singh |
Python3
# Python program to find the sum of elements# of an AP in the given range# Function to find sum in the given rangedef findSum(arr, n, left, right): # Find the value of k k = right - left; # Find the common difference d = arr[1] - arr[0]; # Find the sum ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) // 2; return ans;# Driver codeif __name__ == '__main__': arr = [ 2, 4, 6, 8, 10, 12, 14, 16 ]; queries = 3; q = [[ 2, 4 ],[ 2, 6 ],[ 5, 6 ]]; n = len(arr); for i in range(queries): print(findSum(arr, n, q[i][0], q[i][1]));# This code is contributed by sapnasingh4991 |
C#
// C# program to find the sum of elements// of an AP in the given rangeusing System;class GFG{ // Function to find sum in the given rangestatic int findSum(int []arr, int n, int left, int right){ // Find the value of k int k = right - left; // Find the common difference int d = arr[1] - arr[0]; // Find the sum int ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans;} // Driver codepublic static void Main(String[] args){ int []arr = { 2, 4, 6, 8, 10, 12, 14, 16 }; int queries = 3; int [,]q = { { 2, 4 }, { 2, 6 }, { 5, 6 } }; 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 PrinciRaj1992 |
Javascript
<script>// JavaScript program to find the sum of elements// of an AP 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; // Find the common difference let d = arr[1] - arr[0]; // Find the sum let ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans;}// Driver Code let arr = [ 2, 4, 6, 8, 10, 12, 14, 16 ]; let queries = 3; let q = [[ 2, 4 ], [ 2, 6 ], [ 5, 6 ]]; let n = arr.length; for (let i = 0; i < queries; i++) document.write(findSum(arr, n, q[i][0], q[i][1]) +"<br/>"); </script> |
Output
18 40 22
Time complexity: O(q), where q is the length of the given queries array.
Auxiliary Space: O(1)
Method 2: Using Prefix Sum
Approach:
- Create a prefix sum array for the given arithmetic series.
- For each query, calculate the sum of the range by subtracting the prefix sum at L-1 from the prefix sum at R.
- Output the sum for each query.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;vector<int> arithmetic_series_sum(int arr[], int N, vector<vector<int>> queries) { // precompute prefix sum int prefixSum[N]; prefixSum[0] = arr[0]; for (int i = 1; i < N; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i]; } // process queries vector<int> ans; for (int i = 0; i < queries.size(); i++) { int L = queries[i][0]; int R = queries[i][1]; int sum = prefixSum[R - 1] - prefixSum[L - 2]; ans.push_back(sum); } return ans;}int main() { int arr[] = {2, 4, 6, 8, 10, 12, 14, 16}; int N = sizeof(arr) / sizeof(arr[0]); // define queries vector<vector<int>> queries = {{2, 4},{2, 6},{5, 6}}; // call function to compute arithmetic series sum for queries vector<int> ans = arithmetic_series_sum(arr, N, queries); // print answers for (int i = 0; i < ans.size(); i++) { cout << ans[i] << endl; } return 0;} |
Java
import java.util.ArrayList;public class GFG { public static ArrayList<Integer> arithmeticSeriesSum( int[] arr, int N, ArrayList<ArrayList<Integer> > queries) { // Precompute prefix sum int[] prefixSum = new int[N]; prefixSum[0] = arr[0]; for (int i = 1; i < N; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i]; } // Process queries ArrayList<Integer> ans = new ArrayList<>(); for (int i = 0; i < queries.size(); i++) { int L = queries.get(i).get(0); int R = queries.get(i).get(1); int sum = prefixSum[R - 1] - (L > 1 ? prefixSum[L - 2] : 0); ans.add(sum); } return ans; } public static void main(String[] args) { int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 }; int N = arr.length; // Define queries ArrayList<ArrayList<Integer> > queries = new ArrayList<>(); queries.add( new ArrayList<>(java.util.Arrays.asList(2, 4))); queries.add( new ArrayList<>(java.util.Arrays.asList(2, 6))); queries.add( new ArrayList<>(java.util.Arrays.asList(5, 6))); // Call function to compute arithmetic series sum // for queries ArrayList<Integer> ans = arithmeticSeriesSum(arr, N, queries); // Print answers for (int i = 0; i < ans.size(); i++) { System.out.println(ans.get(i)); } }} |
Python3
def arithmetic_series_sum(arr, N, queries): # precompute prefix sum prefixSum = [0] * N prefixSum[0] = arr[0] for i in range(1, N): prefixSum[i] = prefixSum[i - 1] + arr[i] # process queries ans = [] for i in range(len(queries)): L = queries[i][0] R = queries[i][1] # Compute the sum using prefix sums sum = prefixSum[R - 1] - prefixSum[L - 2] ans.append(sum) return ansif __name__ == "__main__": arr = [2, 4, 6, 8, 10, 12, 14, 16] N = len(arr) # define queries queries = [[2, 4], [2, 6], [5, 6]] # call function to compute arithmetic series sum for queries ans = arithmetic_series_sum(arr, N, queries) # print answers for i in range(len(ans)): print(ans[i]) |
C#
using System;using System.Collections.Generic;class GFG{ static List<int> ArithmeticSeriesSum(int[] arr, int N, List<List<int>> queries) { // precompute prefix sum int[] prefixSum = new int[N]; prefixSum[0] = arr[0]; for (int i = 1; i < N; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i]; } // process queries List<int> ans = new List<int>(); for (int i = 0; i < queries.Count; i++) { int L = queries[i][0]; int R = queries[i][1]; int sum = prefixSum[R - 1] - (L - 2 >= 0 ? prefixSum[L - 2] : 0); ans.Add(sum); } return ans; } static void Main() { int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 }; int N = arr.Length; // define queries List<List<int>> queries = new List<List<int>> { new List<int> { 2, 4 }, new List<int> { 2, 6 }, new List<int> { 5, 6 } }; // call function to compute arithmetic series sum for queries List<int> ans = ArithmeticSeriesSum(arr, N, queries); // print answers foreach (int value in ans) { Console.WriteLine(value); } }} |
Javascript
function arithmeticSeriesSum(arr, N, queries) { // precompute prefix sum let prefixSum = []; prefixSum[0] = arr[0]; for (let i = 1; i < N; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i]; } // process queries let ans = []; for (let i = 0; i < queries.length; i++) { let L = queries[i][0]; let R = queries[i][1]; let sum = prefixSum[R - 1] - (L > 1 ? prefixSum[L - 2] : 0); ans.push(sum); } return ans;}let arr = [2, 4, 6, 8, 10, 12, 14, 16];let N = arr.length;// define querieslet queries = [[2, 4], [2, 6], [5, 6]];// call function to compute arithmetic series sum for querieslet ans = arithmeticSeriesSum(arr, N, queries);// print answersfor (let i = 0; i < ans.length; i++) { console.log(ans[i]);} |
Output
18 40 22
Time complexity: O(N + Q),N is the size of the arithmetic series and Q is the number of queries.
Auxiliary Space: O(N) for the prefix sum array.
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!
