Given an array arr[] of N integers and matrix Queries[][] consisting of Q queries of the form {m, a, b}. For each query the task is to find the sum of array elements according to the following conditions:
- If m = 1: Find the sum of the array elements in the range [a, b].
- If m = 2: Rearrange the array elements in increasing order and find the sum of the elements in the range [a, b] in the new array.
Examples:
Input: arr[] = {6, 4, 2, 7, 2, 7}, Q = 3, Queries[][3] = {{2, 3, 6}, {1, 3, 4}, {1, 1, 6}}
Output: 24 9 28
Explanation:
For Query 1:
m is 2, then array after sorting is arr[] = {2, 2, 4, 6, 7, 7} and sum of element in the range [3, 6] is 4 + 6 + 7 + 7 = 24.
For Query 2:
m is 1, then original array is arr[] = {6, 4, 2, 7, 2, 7} and sum of element in the range [3, 4] is 2 + 7 = 9.
For Query 3:
m is 1, then original array is arr[] = {6, 4, 2, 7, 2, 7} and sum of element in the range [1, 6] is 6 + 4 + 2 + 7 + 2 + 7 = 28.Input: arr[] = {5, 5, 2, 3}, Q = 3, Queries[][10] = {{1, 2, 4}, {2, 1, 4}, {1, 1, 1}, {2, 1, 4}, {2, 1, 2}, {1, 1, 1}, {1, 3, 3}, {1, 1, 3}, {1, 4, 4}, {1, 2, 2}}
Output: 10 15 5 15 5 5 2 12 3 5
Naive Approach: The idea is to traverse the given queries and find the sum of all the elements according to the given conditions:
- Choose the array according to the given m, if m is equal to 1 then choose the original array otherwise choose the other array where all the elements of the array arr[] are sorted.
- Now calculate the sum of the array between the range [a, b].
- Iterate a loop over the range to find the sum.
- Print the sum for each query.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum// between the given range as per// value of mint range_sum(vector<int> v, int a, int b){ // Stores the sum int sum = 0; // Loop to calculate the sum for (int i = a - 1; i < b; i++) { sum += v[i]; } // Return sum return sum;}// Function to find the sum of elements// for each queryvoid findSum(vector<int>& v1, int q, int Queries[][3]){ // Take a dummy vector vector<int> v2; // Size of vector int n = sizeof(v1) / sizeof(int); // Copying the elements into // dummy vector for (int i = 0; i < n; i++) { v2.push_back(v1[i]); } // Sort the dummy vector sort(v2.begin(), v2.end()); // Performs operations for (int i = 0; i < q; i++) { int m = Queries[i][0]; int a = Queries[i][1]; int b = Queries[i][2]; if (m == 1) { // Function Call to find sum cout << range_sum(v1, a, b) << ' '; } else if (m == 2) { // Function Call to find sum cout << range_sum(v2, a, b) << ' '; } }}// Driver Codeint main(){ // Given arr[] vector<int> arr = { 6, 4, 2, 7, 2, 7 }; int Q = 1; // Given Queries int Queries[][3] = { { 2, 3, 6 } }; // Function Call findSum(arr, Q, Queries); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to calculate the sum// between the given range as per// value of mstatic int range_sum(Vector<Integer> v, int a, int b){ // Stores the sum int sum = 0; // Loop to calculate the sum for(int i = a - 1; i < b; i++) { sum += v.get(i); } // Return sum return sum;}static int range_sum(int []v, int a, int b){ // Stores the sum int sum = 0; // Loop to calculate the sum for(int i = a - 1; i < b; i++) { sum += v[i]; } // Return sum return sum;}// Function to find the sum of elements// for each querystatic void findSum(int []v1, int q, int Queries[][]){ // Take a dummy vector Vector<Integer> v2 = new Vector<Integer>(); // Size of vector int n = v1.length; // Copying the elements into // dummy vector for(int i = 0; i < n; i++) { v2.add(v1[i]); } // Sort the dummy vector Collections.sort(v2); // Performs operations for(int i = 0; i < q; i++) { int m = Queries[i][0]; int a = Queries[i][1]; int b = Queries[i][2]; if (m == 1) { // Function call to find sum System.out.print(range_sum( v1, a, b) + " "); } else if (m == 2) { // Function call to find sum System.out.print(range_sum( v2, a, b) + " "); } }}// Driver Codepublic static void main(String[] args){ // Given arr[] int []arr = { 6, 4, 2, 7, 2, 7 }; int Q = 1; // Given Queries int Queries[][] = { { 2, 3, 6 } }; // Function call findSum(arr, Q, Queries);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to calculate the sum# between the given range as per# value of mdef range_sum(v, a, b): # Stores the sum Sum = 0 # Loop to calculate the sum for i in range(a - 1, b): Sum += v[i] # Return sum return Sum # Function to find the sum of elements# for each querydef findSum(v1, q, Queries): # Take a dummy vector v2 = [] # Size of vector n = len(v1) # Copying the elements into # dummy vector for i in range(n): v2.append(v1[i]) # Sort the dummy vector v2.sort() # Performs operations for i in range(q): m = Queries[i][0] a = Queries[i][1] b = Queries[i][2] if (m == 1): # Function call to find sum print(range_sum(v1, a, b), end = " ") elif (m == 2): # Function call to find sum print(range_sum(v2, a, b), end = " ")# Driver code# Given arr[]arr = [ 6, 4, 2, 7, 2, 7 ] Q = 1 # Given QueriesQueries = [ [ 2, 3, 6 ] ] # Function callfindSum(arr, Q, Queries)# This code is contributed divyeshrabadiya07 |
C#
// C# program for the above approachusing System; using System.Collections; using System.Collections.Generic; using System.Text; class GFG{ // Function to calculate the sum// between the given range as per// value of mstatic int range_sum(ArrayList v, int a, int b){ // Stores the sum int sum = 0; // Loop to calculate the sum for(int i = a - 1; i < b; i++) { sum += (int)v[i]; } // Return sum return sum;}// Function to find the sum of elements// for each querystatic void findSum(ArrayList v1, int q, int [,]Queries){ // Take a dummy vector ArrayList v2 = new ArrayList(); // Size of vector int n = v1.Count; // Copying the elements into // dummy vector for(int i = 0; i < n; i++) { v2.Add(v1[i]); } // Sort the dummy vector v2.Sort(); // Performs operations for(int i = 0; i < q; i++) { int m = Queries[i, 0]; int a = Queries[i, 1]; int b = Queries[i, 2]; if (m == 1) { // Function call to find sum Console.Write(range_sum(v1, a, b)); Console.Write(' '); } else if (m == 2) { // Function call to find sum Console.Write(range_sum(v2, a, b)); Console.Write(' '); } }}// Driver Codepublic static void Main(string[] args){ // Given arr[] ArrayList arr=new ArrayList(){ 6, 4, 2, 7, 2, 7 }; int Q = 1; // Given Queries int [,]Queries = { { 2, 3, 6 } }; // Function call findSum(arr, Q, Queries);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program for the above approach// Function to calculate the sum// between the given range as per// value of mfunction range_sum(v, a, b){ // Stores the sum let sum = 0; // Loop to calculate the sum for(let i = a - 1; i < b; i++) { sum += v[i]; } // Return sum return sum;}// Function to find the sum of elements// for each queryfunction findSum(v1, q, Queries){ // Take a dummy vector let v2 = []; // Size of vector let n = v1.length; // Copying the elements into // dummy vector for(let i = 0; i < n; i++) { v2.push(v1[i]); } // Sort the dummy vector v2.sort(function(a, b){return a - b;}); // Performs operations for(let i = 0; i < q; i++) { let m = Queries[i][0]; let a = Queries[i][1]; let b = Queries[i][2]; if (m == 1) { // Function call to find sum document.write(range_sum( v1, a, b) + " "); } else if (m == 2) { // Function call to find sum document.write(range_sum( v2, a, b) + " "); } }}// Driver Code// Given arr[]let arr = [ 6, 4, 2, 7, 2, 7 ];let Q = 1;// Given Querieslet Queries = [ [ 2, 3, 6 ] ];// Function callfindSum(arr, Q, Queries);// This code is contributed by avanitrachhadiya2155</script> |
Output:
24
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by reducing one loop using the prefix sum array. Below are the steps:
- Create the other array brr[] to store the elements of the given array arr[] in sorted order.
- Find the prefix sum of both the arrays arr[] and brr[].
- Traverse the given queries and if the query is of type 1 then the sum of the element in the range [a, b] is given by:
arr[b – 1] – arr[a – 2]
- If the query is of type 2 then the sum of the element in the range [a, b] is given by:
brr[b – 1] – arr[a – 2]
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum// between the given range as per// value of mint range_sum(vector<int>& arr, int a, int b){ // Stores the sum int sum = 0; // Condition for a to print the // sum between ranges [a, b] if (a - 2 < 0) sum = arr[b - 1]; else sum = arr[b - 1] - arr[a - 2]; // Return sum return sum;}// Function to precalculate the sum// of both the vectorsvoid precompute_sum(vector<int>& arr, vector<int>& brr){ int N = (int)arr.size(); // Make Prefix sum array for (int i = 1; i <= N; i++) { arr[i] = arr[i] + arr[i - 1]; brr[i] = brr[i] + brr[i - 1]; }}// Function to compute the result// for each queryvoid find_sum(vector<int>& arr, int q, int Queries[][3]){ // Take a dummy vector and copy // the element of arr in brr vector<int> brr(arr); int N = (int)arr.size(); // Sort the dummy vector sort(brr.begin(), brr.end()); // Compute prefix sum of both vectors precompute_sum(arr, brr); // Performs operations for (int i = 0; i < q; i++) { int m = Queries[i][0]; int a = Queries[i][1]; int b = Queries[i][2]; if (m == 1) { // Function Call to find sum cout << range_sum(arr, a, b) << ' '; } else if (m == 2) { // Function Call to find sum cout << range_sum(brr, a, b) << ' '; } }}// Driver Codeint main(){ // Given arr[] vector<int> arr = { 0, 6, 4, 2, 7, 2, 7 }; // Number of queries int Q = 1; // Given queries int Queries[][3] = { { 2, 3, 6 } }; // Function Call find_sum(arr, Q, Queries); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG{ // Function to calculate the sum// between the given range as per// value of mstatic int range_sum(int []arr, int a, int b){ // Stores the sum int sum = 0; // Condition for a to print the // sum between ranges [a, b] if (a - 2 < 0) sum = arr[b - 1]; else sum = arr[b - 1] - arr[a - 2]; // Return sum return sum;} // Function to precalculate the sum// of both the vectorsstatic void precompute_sum(int []arr, int []brr){ int N = (int)arr.length; // Make Prefix sum array for(int i = 1; i < N; i++) { arr[i] = arr[i] + arr[i - 1]; brr[i] = brr[i] + brr[i - 1]; }} // Function to compute the result// for each querystatic void find_sum(int []arr, int q, int Queries[][]){ // Take a dummy vector and copy // the element of arr in brr int []brr = arr.clone(); int N = (int)arr.length; // Sort the dummy vector Arrays.sort(brr); // Compute prefix sum of both vectors precompute_sum(arr, brr); // Performs operations for(int i = 0; i < q; i++) { int m = Queries[i][0]; int a = Queries[i][1]; int b = Queries[i][2]; if (m == 1) { // Function call to find sum System.out.print(range_sum( arr, a, b) + " "); } else if (m == 2) { // Function call to find sum System.out.print(range_sum( brr, a, b) + " "); } }} // Driver Codepublic static void main(String[] args){ // Given arr[] int []arr = { 0, 6, 4, 2, 7, 2, 7 }; // Number of queries int Q = 1; // Given queries int Queries[][] = { { 2, 3, 6 } }; // Function call find_sum(arr, Q, Queries);}} // This code is contributed by Amit Katiyar |
Python3
# Python3 program for # the above approach# Function to calculate # the sum between the # given range as per value # of mdef range_sum(arr, a, b): # Stores the sum sum = 0 # Condition for a to # print the sum between # ranges [a, b] if (a - 2 < 0): sum = arr[b - 1] else: sum = (arr[b - 1] - arr[a - 2]) # Return sum return sum# Function to precalculate # the sum of both the vectorsdef precompute_sum(arr, brr): N = len(arr) # Make Prefix sum array for i in range(1, N): arr[i] = arr[i] + arr[i - 1] brr[i] = brr[i] + brr[i - 1]# Function to compute # the result for each querydef find_sum(arr, q, Queries): # Take a dummy vector # and copy the element # of arr in brr brr = arr.copy() N = len(arr) # Sort the dummy vector brr.sort() # Compute prefix sum of # both vectors precompute_sum(arr, brr) # Performs operations for i in range(q): m = Queries[i][0] a = Queries[i][1] b = Queries[i][2] if (m == 1): # Function Call to # find sum print (range_sum(arr, a, b), end = ' ') elif (m == 2): # Function Call to # find sum print (range_sum(brr, a, b), end = ' ')# Driver Codeif __name__ == "__main__": # Given arr[] arr = [0, 6, 4, 2, 7, 2, 7] # Number of queries Q = 1 # Given queries Queries = [[2, 3, 6]] # Function Call find_sum(arr, Q, Queries)# This code is contributed by Chitranayal |
C#
// C# program for // the above approachusing System;class GFG{ // Function to calculate the sum// between the given range as per// value of mstatic int range_sum(int []arr, int a, int b){ // Stores the sum int sum = 0; // Condition for a to print the // sum between ranges [a, b] if (a - 2 < 0) sum = arr[b - 1]; else sum = arr[b - 1] - arr[a - 2]; // Return sum return sum;} // Function to precalculate the sum// of both the vectorsstatic void precompute_sum(int []arr, int []brr){ int N = (int)arr.Length; // Make Prefix sum array for(int i = 1; i < N; i++) { arr[i] = arr[i] + arr[i - 1]; brr[i] = brr[i] + brr[i - 1]; }} // Function to compute the result// for each querystatic void find_sum(int []arr, int q, int [,]Queries){ // Take a dummy vector and copy // the element of arr in brr int []brr = new int[arr.Length]; arr.CopyTo(brr, 0); int N = (int)arr.Length; // Sort the dummy vector Array.Sort(brr); // Compute prefix sum of both vectors precompute_sum(arr, brr); // Performs operations for(int i = 0; i < q; i++) { int m = Queries[i, 0]; int a = Queries[i, 1]; int b = Queries[i, 2]; if (m == 1) { // Function call to find sum Console.Write(range_sum( arr, a, b) + " "); } else if (m == 2) { // Function call to find sum Console.Write(range_sum( brr, a, b) + " "); } }} // Driver Codepublic static void Main(String[] args){ // Given []arr int []arr = {0, 6, 4, 2, 7, 2, 7}; // Number of queries int Q = 1; // Given queries int [,]Queries = {{2, 3, 6}}; // Function call find_sum(arr, Q, Queries);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to calculate the sum// between the given range as per// value of mfunction range_sum(arr,a,b){ // Stores the sum let sum = 0; // Condition for a to print the // sum between ranges [a, b] if (a - 2 < 0) sum = arr[b - 1]; else sum = arr[b - 1] - arr[a - 2]; // Return sum return sum;}// Function to precalculate the sum// of both the vectorsfunction precompute_sum(arr,brr){ let N = arr.length; // Make Prefix sum array for(let i = 1; i < N; i++) { arr[i] = arr[i] + arr[i - 1]; brr[i] = brr[i] + brr[i - 1]; }}// Function to compute the result// for each queryfunction find_sum(arr,q,Queries){ // Take a dummy vector and copy // the element of arr in brr let brr = [...arr]; let N = arr.length; // Sort the dummy vector brr.sort(function(a,b){return a-b;}); // Compute prefix sum of both vectors precompute_sum(arr, brr); // Performs operations for(let i = 0; i < q; i++) { let m = Queries[i][0]; let a = Queries[i][1]; let b = Queries[i][2]; if (m == 1) { // Function call to find sum document.write(range_sum( arr, a, b) + " "); } else if (m == 2) { // Function call to find sum document.write(range_sum( brr, a, b) + " "); } }}// Driver Codelet arr=[0, 6, 4, 2, 7, 2, 7];// Number of querieslet Q = 1;// Given querieslet Queries = [[ 2, 3, 6 ]];// Function callfind_sum(arr, Q, Queries);// This code is contributed by rag2127</script> |
Output:
19
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
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!
