Range sum queries for anticlockwise rotations of Array by K indices
Given an array arr consisting of N elements and Q queries of the following two types:
- 1 K: For this type of query, the array needs to be rotated by K indices anticlockwise from its current state.
- 2 L R: For this query, the sum of the array elements present in the indices [L, R] needs to be calculated.
Example:
Input: arr = { 1, 2, 3, 4, 5, 6 }, query = { {2, 1, 3}, {1, 3}, {2, 0, 3}, {1, 4}, {2, 3, 5} }
Output:
9
16
12
Explanation:
For the 1st query {2, 1, 3} -> Sum of the elements in the indices [1, 3] = 2 + 3 + 4 = 9.
For the 2nd query {1, 3} -> Modified array after anti-clockwise rotation by 3 places is { 4, 5, 6, 1, 2, 3 }
For the 3rd query {2, 0, 3} -> Sum of the elements in the indices [0, 3] = 4 + 5 + 6 + 1 = 16.
For the 4th query {1, 4} -> Modified array after anti-clockwise rotation by 4 places is { 2, 3, 4, 5, 6, 1 }
For the 5th query {2, 3, 5} -> Sum of the elements in the indices [3, 5] = 5 + 6 + 1 = 12.
Approach:
- Create a prefix array which is double the size of the arr and copy the element at the ith index of arr to ith and N + ith index of prefix for all i in [0, N).
- Precompute the prefix sum for every index of that array and store in prefix.
- Set the pointer start at 0 to denote the starting index of the initial array.
- For query of type 1, shift start to
((start + K) % N)th position
- For query of type 2, calculate
prefix[start + R] - prefix[start + L- 1 ]
- if start + L >= 1 or print the value of
prefix[start + R]
- otherwise.
Below code is the implementation of the above approach:
C++
// C++ Program to calculate range sum// queries for anticlockwise// rotations of array by K#include <bits/stdc++.h>using namespace std;// Function to execute the queriesvoid rotatedSumQuery( int arr[], int n, vector<vector<int> >& query, int Q){ // Construct a new array // of size 2*N to store // prefix sum of every index int prefix[2 * n]; // Copy elements to the new array for (int i = 0; i < n; i++) { prefix[i] = arr[i]; prefix[i + n] = arr[i]; } // Calculate the prefix sum // for every index for (int i = 1; i < 2 * n; i++) prefix[i] += prefix[i - 1]; // Set start pointer as 0 int start = 0; for (int q = 0; q < Q; q++) { // Query to perform // anticlockwise rotation if (query[q][0] == 1) { int k = query[q][1]; start = (start + k) % n; } // Query to answer range sum else if (query[q][0] == 2) { int L, R; L = query[q][1]; R = query[q][2]; // If pointing to 1st index if (start + L == 0) // Display the sum upto start + R cout << prefix[start + R] << endl; else // Subtract sum upto start + L - 1 // from sum upto start + R cout << prefix[start + R] - prefix[start + L - 1] << endl; } }}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; // Number of query int Q = 5; // Store all the queries vector<vector<int> > query = { { 2, 1, 3 }, { 1, 3 }, { 2, 0, 3 }, { 1, 4 }, { 2, 3, 5 } }; int n = sizeof(arr) / sizeof(arr[0]); rotatedSumQuery(arr, n, query, Q); return 0;} |
Java
// Java program to calculate range sum// queries for anticlockwise// rotations of array by Kclass GFG{// Function to execute the queriesstatic void rotatedSumQuery(int arr[], int n, int [][]query, int Q){ // Construct a new array // of size 2*N to store // prefix sum of every index int []prefix = new int[2 * n]; // Copy elements to the new array for(int i = 0; i < n; i++) { prefix[i] = arr[i]; prefix[i + n] = arr[i]; } // Calculate the prefix sum // for every index for(int i = 1; i < 2 * n; i++) prefix[i] += prefix[i - 1]; // Set start pointer as 0 int start = 0; for(int q = 0; q < Q; q++) { // Query to perform // anticlockwise rotation if (query[q][0] == 1) { int k = query[q][1]; start = (start + k) % n; } // Query to answer range sum else if (query[q][0] == 2) { int L, R; L = query[q][1]; R = query[q][2]; // If pointing to 1st index if (start + L == 0) // Display the sum upto start + R System.out.print(prefix[start + R] + "\n"); else // Subtract sum upto start + L - 1 // from sum upto start + R System.out.print(prefix[start + R] - prefix[start + L - 1] + "\n"); } }}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 4, 5, 6 }; // Number of query int Q = 5; // Store all the queries int [][]query = { { 2, 1, 3 }, { 1, 3 }, { 2, 0, 3 }, { 1, 4 }, { 2, 3, 5 } }; int n = arr.length; rotatedSumQuery(arr, n, query, Q);}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to calculate range sum# queries for anticlockwise# rotations of the array by K# Function to execute the queriesdef rotatedSumQuery(arr, n, query, Q): # Construct a new array # of size 2*N to store # prefix sum of every index prefix = [0] * (2 * n) # Copy elements to the new array for i in range(n): prefix[i] = arr[i] prefix[i + n] = arr[i] # Calculate the prefix sum # for every index for i in range(1, 2 * n): prefix[i] += prefix[i - 1]; # Set start pointer as 0 start = 0; for q in range(Q): # Query to perform # anticlockwise rotation if (query[q][0] == 1): k = query[q][1] start = (start + k) % n; # Query to answer range sum elif (query[q][0] == 2): L = query[q][1] R = query[q][2] # If pointing to 1st index if (start + L == 0): # Display the sum upto start + R print(prefix[start + R]) else: # Subtract sum upto start + L - 1 # from sum upto start + R print(prefix[start + R]- prefix[start + L - 1]) # Driver codearr = [ 1, 2, 3, 4, 5, 6 ];# Number of queryQ = 5# Store all the queriesquery= [ [ 2, 1, 3 ], [ 1, 3 ], [ 2, 0, 3 ], [ 1, 4 ], [ 2, 3, 5 ] ]n = len(arr);rotatedSumQuery(arr, n, query, Q);# This code is contributed by ankitkumar34 |
C#
// C# program to calculate range sum// queries for anticlockwise// rotations of array by Kusing System;class GFG{// Function to execute the queriesstatic void rotatedSumQuery(int[] arr, int n, int[,] query, int Q){ // Construct a new array // of size 2*N to store // prefix sum of every index int[] prefix = new int[2 * n]; // Copy elements to the new array for(int i = 0; i < n; i++) { prefix[i] = arr[i]; prefix[i + n] = arr[i]; } // Calculate the prefix sum // for every index for(int i = 1; i < 2 * n; i++) prefix[i] += prefix[i - 1]; // Set start pointer as 0 int start = 0; for(int q = 0; q < Q; q++) { // Query to perform // anticlockwise rotation if (query[q, 0] == 1) { int k = query[q, 1]; start = (start + k) % n; } // Query to answer range sum else if (query[q, 0] == 2) { int L, R; L = query[q, 1]; R = query[q, 2]; // If pointing to 1st index if (start + L == 0) // Display the sum upto start + R Console.Write(prefix[start + R] + "\n"); else // Subtract sum upto start + L - 1 // from sum upto start + R Console.Write(prefix[start + R] - prefix[start + L - 1] + "\n"); } }}// Driver codepublic static void Main(){ int[] arr = new int[] { 1, 2, 3, 4, 5, 6 }; // Number of query int Q = 5; // Store all the queries int[,] query = new int[,] { { 2, 1, 3 }, { 1, 3, 0 }, { 2, 0, 3 }, { 1, 4, 0 }, { 2, 3, 5 } }; int n = arr.Length; rotatedSumQuery(arr, n, query, Q);}}// This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program to calculate range sum// queries for anticlockwise// rotations of array by K// Function to execute the queriesfunction rotatedSumQuery(arr, n, query, Q){ // Construct a new array // of size 2*N to store // prefix sum of every index let prefix = []; // Copy elements to the new array for(let i = 0; i < n; i++) { prefix[i] = arr[i]; prefix[i + n] = arr[i]; } // Calculate the prefix sum // for every index for(let i = 1; i < 2 * n; i++) prefix[i] += prefix[i - 1]; // Set start pointer as 0 let start = 0; for(let q = 0; q < Q; q++) { // Query to perform // anticlockwise rotation if (query[q][0] == 1) { let k = query[q][1]; start = (start + k) % n; } // Query to answer range sum else if (query[q][0] == 2) { let L, R; L = query[q][1]; R = query[q][2]; // If pointing to 1st index if (start + L == 0) // Display the sum upto start + R document.write(prefix[start + R] + "<br/>"); else // Subtract sum upto start + L - 1 // from sum upto start + R document.write(prefix[start + R] - prefix[start + L - 1] + "<br/>"); } }} // Driver code let arr = [ 1, 2, 3, 4, 5, 6 ]; // Number of query let Q = 5; // Store all the queries let query = [[ 2, 1, 3 ], [ 1, 3 ], [ 2, 0, 3 ], [ 1, 4 ], [ 2, 3, 5 ]]; let n = arr.length; rotatedSumQuery(arr, n, query, Q); // This code is contributed by susmitakundugoaldanga.</script> |
Output:
9 16 12
Time Complexity: O(N+Q), where Q is the number of queries, and as each query will cost O (1) time for Q queries time complexity would be O(N+Q).
Auxiliary Space: O(N), as we are using extra space for prefix.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
