Queries to calculate the Sum of Array elements in the range [L, R] having indices as multiple of K

0 0 10 minutes read

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 = 21

Input: 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 j^th 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 Query
struct 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 query
int 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 Code
int 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 approach
import java.util.*;
 
class GFG{
 
// Structure of a Query
static 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 query
static 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 Code
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];
    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 approach
using System;
 
class GFG{
 
// Structure of a Query
class 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 query
static 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 Code
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];
    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(N² + O(Q)), Computing the prefix sum array requires O(N²) computational complexity and each query requires O(1) computational complexity.
Auxiliary Space: O(N²)

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 Query
struct 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 query
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
          cout<<answer<<endl;
    }
}
 
// Driver Code
int 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 approach
import java.io.*;
 
// Structure of a Query
class 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 Query
class 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 query
def 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 Code
if __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 approach
 
using 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 Query
class 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 query
function 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 Code
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);

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 zambiatek!