Given an array arr[] consisting of N integers, and a matrix Q[][] consisting of queries of the form (L, R, K), the task for each query is to calculate the sum of array elements from the range [L, R] which are present at indices(0- based indexing) which are multiples of K and
Examples:
Input: arr[]={1, 2, 3, 4, 5, 6}, Q[][]={{2, 5, 2}, {0, 5, 1}}
Output:
8
21
Explanation:
Query1: Indexes (2, 4) are multiple of K(= 2) from the range [2, 5]. Therefore, required Sum = 3+5 = 8.
Query2: Since all indices are a multiple of K(= 1), therefore, the required sum from the range [0, 5] = 1 + 2 + 3 + 4 + 5 + 6 = 21Input: arr[]={4, 3, 5, 1, 9}, Q[][]={{1, 4, 1}, {3, 4, 3}}
Output:
18
1
Approach: The problem can be solved using Prefix Sum Array and Range sum query technique. Follow the steps below to solve the problem:
- Initialize a matrix of size prefixSum[][] such that prefixSum[i][j] stores the sum of elements present in indices which are a multiple of i up to jth index.
- Traverse the array and precompute the prefix sums.
- Traverse each query, and print the result of prefixSum[K][R] – prefixSum[K][L – 1].
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of a Querystruct Node { int L; int R; int K;};// Function to calculate the sum of array// elements at indices from range [L, R]// which are multiples of K for each queryint kMultipleSum(int arr[], Node Query[], int N, int Q){ // Stores Prefix Sum int prefixSum[N + 1][N]; // prefixSum[i][j] : Stores the sum from // indices [0, j] which are multiples of i for (int i = 1; i <= N; i++) { prefixSum[i][0] = arr[0]; for (int j = 0; j < N; j++) { // If index j is a multiple of i if (j % i == 0) { // Compute prefix sum prefixSum[i][j] = arr[j] + prefixSum[i][j - 1]; } // Otherwise else { prefixSum[i][j] = prefixSum[i][j - 1]; } } } // Traverse each query for (int i = 0; i < Q; i++) { // Sum of all indices upto R which // are a multiple of K int last = prefixSum[Query[i].K][Query[i].R]; int first; // Sum of all indices upto L - 1 which // are a multiple of K if (Query[i].L == 0) { first = prefixSum[Query[i].K][Query[i].L]; } else { first = prefixSum[Query[i].K][Query[i].L - 1]; } // Calculate the difference cout << last - first << endl; }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); int Q = 2; Node Query[Q]; Query[0].L = 2, Query[0].R = 5, Query[0].K = 2; Query[1].L = 3, Query[1].R = 5, Query[1].K = 5; kMultipleSum(arr, Query, N, Q);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Structure of a Querystatic class Node{ int L; int R; int K;};// Function to calculate the sum of array// elements at indices from range [L, R]// which are multiples of K for each querystatic void kMultipleSum(int arr[], Node Query[], int N, int Q){ // Stores Prefix Sum int prefixSum[][] = new int[N + 1][N]; // prefixSum[i][j] : Stores the sum from // indices [0, j] which are multiples of i for(int i = 1; i <= N; i++) { prefixSum[i][0] = arr[0]; for(int j = 0; j < N; j++) { // If index j is a multiple of i if (j % i == 0) { // Compute prefix sum if (j != 0) prefixSum[i][j] = arr[j] + prefixSum[i][j - 1]; } // Otherwise else { prefixSum[i][j] = prefixSum[i][j - 1]; } } } // Traverse each query for(int i = 0; i < Q; i++) { // Sum of all indices upto R which // are a multiple of K int last = prefixSum[Query[i].K][Query[i].R]; int first; // Sum of all indices upto L - 1 which // are a multiple of K if (Query[i].L == 0) { first = prefixSum[Query[i].K][Query[i].L]; } else { first = prefixSum[Query[i].K][Query[i].L - 1]; } // Calculate the difference System.out.print(last - first + "\n"); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = arr.length; int Q = 2; Node Query[] = new Node[Q]; for(int i = 0; i < Q; i++) Query[i] = new Node(); Query[0].L = 2; Query[0].R = 5; Query[0].K = 2; Query[1].L = 3; Query[1].R = 5; Query[1].K = 5; kMultipleSum(arr, Query, N, Q);}}// This code is contributed by 29AjayKumar |
Python3
class GFG : # Structure of a Query class Node : L = 0 R = 0 K = 0 # Function to calculate the sum of array # elements at indices from range [L, R] # which are multiples of K for each query @staticmethod def kMultipleSum( arr, Query, N, Q) : # Stores Prefix Sum prefixSum = [[0] * (N) for _ in range(N + 1)] # prefixSum[i][j] : Stores the sum from # indices [0, j] which are multiples of i i = 1 while (i <= N) : prefixSum[i][0] = arr[0] j = 0 while (j < N) : # If index j is a multiple of i if (j % i == 0) : # Compute prefix sum if (j != 0) : prefixSum[i][j] = arr[j] + prefixSum[i][j - 1] else : prefixSum[i][j] = prefixSum[i][j - 1] j += 1 i += 1 # Traverse each query i = 0 while (i < Q) : # Sum of all indices upto R which # are a multiple of K last = prefixSum[Query[i].K][Query[i].R] first = 0 # Sum of all indices upto L - 1 which # are a multiple of K if (Query[i].L == 0) : first = prefixSum[Query[i].K][Query[i].L] else : first = prefixSum[Query[i].K][Query[i].L - 1] # Calculate the difference print(str(last - first) + "\n", end ="") i += 1 # Driver Code @staticmethod def main( args) : arr = [1, 2, 3, 4, 5, 6] N = len(arr) Q = 2 Query = [None] * (Q) i = 0 while (i < Q) : Query[i] = GFG.Node() i += 1 Query[0].L = 2 Query[0].R = 5 Query[0].K = 2 Query[1].L = 3 Query[1].R = 5 Query[1].K = 5 GFG.kMultipleSum(arr, Query, N, Q) if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# program to implement// the above approachusing System;class GFG{// Structure of a Queryclass Node{ public int L; public int R; public int K;};// Function to calculate the sum of array// elements at indices from range [L, R]// which are multiples of K for each querystatic void kMultipleSum(int []arr, Node []Query, int N, int Q){ // Stores Prefix Sum int [,]prefixSum = new int[N + 1, N]; // prefixSum[i,j] : Stores the sum from // indices [0, j] which are multiples of i for(int i = 1; i <= N; i++) { prefixSum[i, 0] = arr[0]; for(int j = 0; j < N; j++) { // If index j is a multiple of i if (j % i == 0) { // Compute prefix sum if (j != 0) prefixSum[i, j] = arr[j] + prefixSum[i, j - 1]; } // Otherwise else { prefixSum[i, j] = prefixSum[i, j - 1]; } } } // Traverse each query for(int i = 0; i < Q; i++) { // Sum of all indices upto R which // are a multiple of K int last = prefixSum[Query[i].K,Query[i].R]; int first; // Sum of all indices upto L - 1 which // are a multiple of K if (Query[i].L == 0) { first = prefixSum[Query[i].K,Query[i].L]; } else { first = prefixSum[Query[i].K,Query[i].L - 1]; } // Calculate the difference Console.Write(last - first + "\n"); }}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; int Q = 2; Node []Query = new Node[Q]; for(int i = 0; i < Q; i++) Query[i] = new Node(); Query[0].L = 2; Query[0].R = 5; Query[0].K = 2; Query[1].L = 3; Query[1].R = 5; Query[1].K = 5; kMultipleSum(arr, Query, N, Q);}}// This code is contributed by 29AjayKumar |
Javascript
class Node { constructor(L, R, K) { this.L = L; this.R = R; this.K = K; }}function kMultipleSum(arr, Query, N, Q){ // Stores Prefix Sum let prefixSum = new Array(N + 1); prefixSum[0] = new Array(N); for (let i = 1; i <= N; i++) { prefixSum[i] = new Array(N); prefixSum[i][0] = arr[0]; for (let j = 1; j < N; j++) { if (j % i === 0) { prefixSum[i][j] = arr[j] + prefixSum[i][j - 1]; } else { prefixSum[i][j] = prefixSum[i][j - 1]; } }} // Traverse each query for (let i = 0; i < Q; i++) { last = prefixSum[Query[i].K][Query[i].R]; if (Query[i].L === 1) { first = prefixSum[Query[i].K][0]; } else { first = prefixSum[Query[i].K][Query[i].L -1]; } console.log(last - first); }}let arr = [ 1, 2, 3, 4, 5, 6 ];let N = arr.length;let Q = 2;let Query=[];Query.push(new Node(2,5,2));Query.push(new Node(3,5,5));//Query[0].L = 2, Query[0].R = 5, Query[0].K = 2;//Query[1].L = 3, Query[1].R = 5, Query[1].K = 5;kMultipleSum(arr, Query, N, Q);// This code is contributed by poojaagarwal2. |
Output
8 6
Time Complexity: O(N2 + O(Q)), Computing the prefix sum array requires O(N2) computational complexity and each query requires O(1) computational complexity.
Auxiliary Space: O(N2)
Method 2:-
- Just traverse all the queries.
- For all the queries traverse the array from L or R.
- Check if the index is divisible by K or not. If yes then and the element into answer.
- In the end of each query print the answer
Solution for the above Approach:-
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of a Querystruct Node { int L; int R; int K;};// Function to calculate the sum of array// elements at indices from range [L, R]// which are multiples of K for each queryvoid kMultipleSum(int arr[], Node Query[], int N, int Q){ //Traversing All Queries for(int j=0;j<Q;j++){ //Taking L into Start int start = Query[j].L; //Taking R into End int end = Query[j].R; int answer=0; for(int i=start;i<=end;i++) { if(i%Query[j].K==0)answer+=arr[i]; } //Printing Answer for Each Query cout<<answer<<endl; }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); int Q = 2; Node Query[Q]; Query[0].L = 2, Query[0].R = 5, Query[0].K = 2; Query[1].L = 3, Query[1].R = 5, Query[1].K = 5; kMultipleSum(arr, Query, N, Q);} |
Java
// Java Program to implement the above approachimport java.io.*;// Structure of a Queryclass Node { int L, R, K; Node(int L, int R, int K) { this.L = L; this.R = R; this.K = K; }}class GFG { // Function to calculate the sum of array elements at // indices from range [L, R] which are multiples of K // for each query static void kMultipleSum(int[] arr, Node[] Query, int N, int Q) { // Traversing All Queries for (int j = 0; j < Q; j++) { // Taking L into Start int start = Query[j].L; // Taking R into End int end = Query[j].R; int answer = 0; for (int i = start; i <= end; i++) { if (i % Query[j].K == 0) answer += arr[i]; } // Printing Answer for Each Query System.out.println(answer); } } public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.length; int Q = 2; Node[] Query = new Node[Q]; Query[0] = new Node(2, 5, 2); Query[1] = new Node(3, 5, 5); kMultipleSum(arr, Query, N, Q); }}// This code is contributed by sankar. |
Python3
# Python Program to implement the above approach# Structure of a Queryclass Node: def __init__(self, L, R, K): self.L = L self.R = R self.K = K# Function to calculate the sum of array# elements at indices from range [L, R]# which are multiples of K for each querydef kMultipleSum(arr, Query, N, Q): # Traversing All Queries for j in range(Q): # Taking L into Start start = Query[j].L # Taking R into End end = Query[j].R answer = 0 for i in range(start, end + 1): if i % Query[j].K == 0: answer += arr[i] # Printing Answer for Each Query print(answer)# Driver Codeif __name__ == '__main__': arr = [1, 2, 3, 4, 5, 6] N = len(arr) Q = 2 Query = [Node(2, 5, 2), Node(3, 5, 5)] kMultipleSum(arr, Query, N, Q) |
C#
// C# Program to implement// the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG { // Structure of a Query class Node { public int L, R, K; public Node(int L, int R, int K) { this.L=L; this.R=R; this.K=K; } } // Function to calculate the sum of array // elements at indices from range [L, R] // which are multiples of K for each query static void kMultipleSum(int[] arr, Node[] Query, int N, int Q) { //Traversing All Queries for(int j=0;j<Q;j++){ //Taking L into Start int start = Query[j].L; //Taking R into End int end = Query[j].R; int answer=0; for(int i=start;i<=end;i++) { if(i%Query[j].K==0) answer+=arr[i]; } //Printing Answer for Each Query Console.WriteLine(answer); } } // Driver Code static public void Main() { int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; int Q = 2; Node[] Query=new Node[Q]; Query[0]=new Node(2,5,2); Query[1]=new Node(3,5,5); kMultipleSum(arr, Query, N, Q); }} |
Javascript
// Javascript Program to implement// the above approach// Structure of a Queryclass Node { constructor(L,R,K) { this.L=L; this.R=R; this.K=K; }}// Function to calculate the sum of array// elements at indices from range [L, R]// which are multiples of K for each queryfunction kMultipleSum(arr, Query, N, Q){ //Traversing All Queries for(let j=0;j<Q;j++){ //Taking L into Start let start = Query[j].L; //Taking R into End let end = Query[j].R; let answer=0; for(let i=start;i<=end;i++) { if(i%Query[j].K==0) answer+=arr[i]; } //Printing Answer for Each Query console.log(answer); }}// Driver Codelet arr = [ 1, 2, 3, 4, 5, 6 ];let N = arr.length;let Q = 2;let Query=[];Query.push(new Node(2,5,2));Query.push(new Node(3,5,5));/*Query[0].L = 2, Query[0].R = 5, Query[0].K = 2;Query[1].L = 3, Query[1].R = 5, Query[1].K = 5;*/kMultipleSum(arr, Query, N, Q); |
Output
8 6
Time Complexity:- O(Q*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!
