Given an array arr[] of N integers and Q queries of the form {X, Y} of the following two types:
- If X = 1, rotate the given array to the left by Y positions.
- If X = 2, print the maximum sum subarray of length Y in the current state of the array.
Examples:
Input: N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2, Query[][] = {{1, 2}, {2, 3}}
Output:
Query 1: 3 4 5 1 2
Query 2: 12
Explanation:
Query 1: Shift array to the left 2 times: {1, 2, 3, 4, 5} -> {2, 3, 4, 5, 1} -> {3, 4, 5, 1, 2}
Query 2: Maximum sum subarray of length 3 is {3, 4, 5} and the sum is 12Input: N = 5, arr[] = {3, 4, 5, 1, 2}, Q = 3, Query[][] = {{1, 3}, {1, 1}, {2, 4}}
Output:
Query 1: 1 2 3 4 5
Query 2: 2 3 4 5 1
Query 3: 14
Explanation:
Query 1: Shift array to the left 3 times: {3, 4, 5, 1, 2} -> {4, 5, 1, 2, 3} -> {5, 1, 2, 3, 4} -> {1, 2, 3, 4, 5}
Query 2: Shift array to the left 1 time: {1, 2, 3, 4, 5} -> {2, 3, 4, 5, 1}
Query 3: Maximum sum subarray of length 4 is {2, 3, 4, 5} and sum is 14
Naive Approach: The simplest approach is to rotate the array by shifting elements one by one up to distance Y for queries is of type 1 and generating the sum of all the subarrays of length Y and print the maximum sum if the query is of type 2.
Time Complexity: O(Q*N*Y)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use the Juggling Algorithm for array rotation and for finding the maximum sum subarray of length Y, use the Sliding Window Technique. Follow the steps below to solve the problem:
- If X = 1, rotate the array by Y, using the Juggling Algorithm.
- Otherwise, if X = 2, find the maximum sum subarray of length Y using the Sliding Window Technique.
- Print the array if query X is 1.
- Otherwise, print the maximum sum subarray of size Y.
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 maximum// sum of length kint MaxSum(vector<int> arr, int n, int k){ int i, max_sum = 0, sum = 0; // Calculating the max sum for // the first k elements for (i = 0; i < k; i++) { sum += arr[i]; } max_sum = sum; // Find subarray with maximum sum while (i < n) { // Update the sum sum = sum - arr[i - k] + arr[i]; if (max_sum < sum) { max_sum = sum; } i++; } // Return maximum sum return max_sum;}// Function to calculate gcd of the// two numbers n1 and n2int gcd(int n1, int n2){ // Base Case if (n2 == 0) { return n1; } // Recursively find the GCD else { return gcd(n2, n1 % n2); }}// Function to rotate the array by Yvector<int> RotateArr(vector<int> arr, int n, int d){ // For handling k >= N int i = 0, j = 0; d = d % n; // Dividing the array into // number of sets int no_of_sets = gcd(d, n); for (i = 0; i < no_of_sets; i++) { int temp = arr[i]; j = i; // Rotate the array by Y while (true) { int k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } // Update arr[j] arr[j] = temp; } // Return the rotated array return arr;}// Function that performs the queries// on the given arrayvoid performQuery(vector<int>& arr, int Q[][2], int q){ int N = (int)arr.size(); // Traverse each query for (int i = 0; i < q; i++) { // If query of type X = 1 if (Q[i][0] == 1) { arr = RotateArr(arr, N, Q[i][1]); // Print the array for (auto t : arr) { cout << t << " "; } cout << "\n"; } // If query of type X = 2 else { cout << MaxSum(arr, N, Q[i][1]) << "\n"; } }}// Driver Codeint main(){ // Given array arr[] vector<int> arr = { 1, 2, 3, 4, 5 }; int q = 5; // Given Queries int Q[][2] = { { 1, 2 }, { 2, 3 }, { 1, 3 }, { 1, 1 }, { 2, 4 } }; // Function Call performQuery(arr, Q, q); return 0;} |
Java
// Java program for // the above approachclass GFG{// Function to calculate the maximum// sum of length kstatic int MaxSum(int []arr, int n, int k){ int i, max_sum = 0, sum = 0; // Calculating the max sum for // the first k elements for (i = 0; i < k; i++) { sum += arr[i]; } max_sum = sum; // Find subarray with maximum sum while (i < n) { // Update the sum sum = sum - arr[i - k] + arr[i]; if (max_sum < sum) { max_sum = sum; } i++; } // Return maximum sum return max_sum;}// Function to calculate gcd // of the two numbers n1 and n2static int gcd(int n1, int n2){ // Base Case if (n2 == 0) { return n1; } // Recursively find the GCD else { return gcd(n2, n1 % n2); }}// Function to rotate the array by Ystatic int []RotateArr(int []arr, int n, int d){ // For handling k >= N int i = 0, j = 0; d = d % n; // Dividing the array into // number of sets int no_of_sets = gcd(d, n); for (i = 0; i < no_of_sets; i++) { int temp = arr[i]; j = i; // Rotate the array by Y while (true) { int k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } // Update arr[j] arr[j] = temp; } // Return the rotated array return arr;}// Function that performs the queries// on the given arraystatic void performQuery(int []arr, int Q[][], int q){ int N = arr.length; // Traverse each query for (int i = 0; i < q; i++) { // If query of type X = 1 if (Q[i][0] == 1) { arr = RotateArr(arr, N, Q[i][1]); // Print the array for (int t : arr) { System.out.print(t + " "); } System.out.print("\n"); } // If query of type X = 2 else { System.out.print(MaxSum(arr, N, Q[i][1]) + "\n"); } }}// Driver Codepublic static void main(String[] args){ // Given array arr[] int []arr = {1, 2, 3, 4, 5}; int q = 5; // Given Queries int Q[][] = {{1, 2}, {2, 3}, {1, 3}, {1, 1}, {2, 4}}; // Function Call performQuery(arr, Q, q);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to calculate the maximum# sum of length kdef MaxSum(arr, n, k): i, max_sum = 0, 0 sum = 0 # Calculating the max sum for # the first k elements while i < k: sum += arr[i] i += 1 max_sum = sum # Find subarray with maximum sum while (i < n): # Update the sum sum = sum - arr[i - k] + arr[i] if (max_sum < sum): max_sum = sum i += 1 # Return maximum sum return max_sum# Function to calculate gcd of the# two numbers n1 and n2def gcd(n1, n2): # Base Case if (n2 == 0): return n1 # Recursively find the GCD else: return gcd(n2, n1 % n2)# Function to rotate the array by Ydef RotateArr(arr, n, d): # For handling k >= N i = 0 j = 0 d = d % n # Dividing the array into # number of sets no_of_sets = gcd(d, n) for i in range(no_of_sets): temp = arr[i] j = i # Rotate the array by Y while (True): k = j + d if (k >= n): k = k - n if (k == i): break arr[j] = arr[k] j = k # Update arr[j] arr[j] = temp # Return the rotated array return arr# Function that performs the queries# on the given arraydef performQuery(arr, Q, q): N = len(arr) # Traverse each query for i in range(q): # If query of type X = 1 if (Q[i][0] == 1): arr = RotateArr(arr, N, Q[i][1]) # Print the array for t in arr: print(t, end = " ") print() # If query of type X = 2 else: print(MaxSum(arr, N, Q[i][1]))# Driver Codeif __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 3, 4, 5 ] q = 5 # Given Queries Q = [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 1, 1 ], [ 2, 4 ] ] # Function call performQuery(arr, Q, q)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate the maximum// sum of length kstatic int MaxSum(int[] arr, int n, int k){ int i, max_sum = 0, sum = 0; // Calculating the max sum for // the first k elements for(i = 0; i < k; i++) { sum += arr[i]; } max_sum = sum; // Find subarray with maximum sum while (i < n) { // Update the sum sum = sum - arr[i - k] + arr[i]; if (max_sum < sum) { max_sum = sum; } i++; } // Return maximum sum return max_sum;} // Function to calculate gcd // of the two numbers n1 and n2static int gcd(int n1, int n2){ // Base Case if (n2 == 0) { return n1; } // Recursively find the GCD else { return gcd(n2, n1 % n2); }} // Function to rotate the array by Ystatic int []RotateArr(int []arr, int n, int d){ // For handling k >= N int i = 0, j = 0; d = d % n; // Dividing the array into // number of sets int no_of_sets = gcd(d, n); for(i = 0; i < no_of_sets; i++) { int temp = arr[i]; j = i; // Rotate the array by Y while (true) { int k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } // Update arr[j] arr[j] = temp; } // Return the rotated array return arr;}// Function that performs the queries// on the given arraystatic void performQuery(int[] arr, int[,] Q, int q){ int N = arr.Length; // Traverse each query for(int i = 0; i < q; i++) { // If query of type X = 1 if (Q[i, 0] == 1) { arr = RotateArr(arr, N, Q[i, 1]); // Print the array for(int t = 0; t < arr.Length; t++) { Console.Write(arr[t] + " "); } Console.WriteLine(); } // If query of type X = 2 else { Console.WriteLine(MaxSum(arr, N, Q[i, 1])); } }}// Driver codestatic void Main(){ // Given array arr[] int[] arr = { 1, 2, 3, 4, 5 }; int q = 5; // Given Queries int[,] Q = { { 1, 2 }, { 2, 3 }, { 1, 3 }, { 1, 1 }, { 2, 4 } }; // Function call performQuery(arr, Q, q);}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// javascript program for // the above approach // Function to calculate the maximum // sum of length k function MaxSum(arr , n , k) { var i, max_sum = 0, sum = 0; // Calculating the max sum for // the first k elements for (i = 0; i < k; i++) { sum += arr[i]; } max_sum = sum; // Find subarray with maximum sum while (i < n) { // Update the sum sum = sum - arr[i - k] + arr[i]; if (max_sum < sum) { max_sum = sum; } i++; } // Return maximum sum return max_sum; } // Function to calculate gcd // of the two numbers n1 and n2 function gcd(n1 , n2) { // Base Case if (n2 == 0) { return n1; } // Recursively find the GCD else { return gcd(n2, n1 % n2); } } // Function to rotate the array by Y function RotateArr(arr , n , d) { // For handling k >= N var i = 0, j = 0; d = d % n; // Dividing the array into // number of sets var no_of_sets = gcd(d, n); for (i = 0; i < no_of_sets; i++) { var temp = arr[i]; j = i; // Rotate the array by Y while (true) { var k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } // Update arr[j] arr[j] = temp; } // Return the rotated array return arr; } // Function that performs the queries // on the given array function performQuery(arr , Q , q) { var N = arr.length; // Traverse each query for (i = 0; i < q; i++) { // If query of type X = 1 if (Q[i][0] == 1) { arr = RotateArr(arr, N, Q[i][1]); // Print var the array for (var t =0 ;t< arr.length;t++) { document.write(arr[t] + " "); } document.write("<br/>"); } // If query of type X = 2 else { document.write(MaxSum(arr, N, Q[i][1]) + "<br/>"); } } } // Driver Code // Given array arr var arr = [ 1, 2, 3, 4, 5 ]; var q = 5; // Given Queries var Q = [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 1, 1 ], [ 2, 4 ] ]; // Function Call performQuery(arr, Q, q);// This code contributed by aashish1995</script> |
Output:
3 4 5 1 2 12 1 2 3 4 5 2 3 4 5 1 14
Time Complexity: O(Q*N), where Q is the number of queries, and N is the size of the given array.
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!
