Given a circular array arr[] of N integers and an integer K, the task is to print the array after the following operations:
- If K is non-negative, then replace A[i] with the sum of the next K elements.
- If K is negative, then replace it with the sum of previous K elements.
A cyclic array means the next element of the last element of the array is the first element and the previous element of the first element is the last element.
Examples:
Input: arr[] = {4, 2, -5, 11}, K = 3
Output: 8 10 17 1
Explanation:
Step 1: For index 0, replace arr[0] = arr[1] + arr[2] + arr[3] = 2 + (-5) + 11 = 8
Step 2: For index 1, replace arr[1] = arr[2] + arr[3] + arr[0] = (-5) + 11 + 4 = 10
Step 3: For index 2, replace arr[2] = arr[3] + arr[0] + arr[1] = 11 + 4 + 2 = 17
Step 4: For index 3, replace arr[3] = arr[0] + arr[1] + arr[2] = 4 + 2 + -5 = 1
Therefore, the resultant array is {8, 10, 17, 1}Input: arr[] = {2, 5, 7, 9}, K = -2
Output: 16 11 7 12
Explanation:
Step 1: For index 0, replace arr[0] = arr[3] + arr[2] = 9 + 7 = 16
Step 2: For index 1, replace arr[1] = arr[0] + arr[3] = 2 + 9 = 11
Step 3: For index 2, replace arr[2] = arr[1] + arr[0] = 5 + 2 = 7
Step 4: For index 3, replace arr[3] = arr[2] + arr[1] = 7 + 5 = 12
Therefore, the resultant array is {16, 11, 7, 12}
Naive Approach: The simplest approach to solve the problem is to traverse the array and traverse the next or previous K elements, based on the value of K, for every array element and print their sum. Follow the steps below to solve the problem:
- If the value of K is negative, then reverse the array and find the sum of the next K elements.
- If the value of K is non-negative, then simply find the sum of the next K elements for each element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define pb push_back// Function to find the sum of next// or previous k array elementsvector<int> sumOfKelementsUtil( vector<int>& a, int x){ // Size of the array int n = a.size(); int count, k, temp; // Stores the result vector<int> ans; // Iterate the given array for (int i = 0; i < n; i++) { count = 0; k = i + 1; temp = 0; // Traverse the k elements while (count < x) { temp += a[k % n]; count++; k++; } // Push the K elements sum ans.pb(temp); } // Return the resultant vector return ans;}// Function that prints the sum of next// K element for each index in the arrayvoid sumOfKelements(vector<int>& arr, int K){ // Size of the array int N = (int)arr.size(); // Stores the result vector<int> ans; // If key is negative, // reverse the array if (K < 0) { K = K * (-1); // Reverse the array reverse(arr.begin(), arr.end()); // Find the resultant vector ans = sumOfKelementsUtil(arr, K); // Reverse the array again to // get the original sequence reverse(ans.begin(), ans.end()); } // If K is positive else { ans = sumOfKelementsUtil(arr, K); } // Print the answer for (int i = 0; i < N; i++) { cout << ans[i] << " "; }}// Driver Codeint main(){ // Given array arr[] vector<int> arr = { 4, 2, -5, 11 }; int K = 3; // Function Call sumOfKelements(arr, K); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{ //reverse arraystatic Vector<Integer> reverse(Vector<Integer> a) { int i, n = a.size(), t; for (i = 0; i < n / 2; i++) { t = a.elementAt(i); a.set(i, a.elementAt(n - i - 1)); a.set(n - i - 1, t); } return a;}// Function to find the sum of next// or previous k array elementsstatic Vector<Integer> sumOfKelementsUtil( Vector<Integer>a, int x){ // Size of the array int n = a.size(); int count, k, temp; // Stores the result Vector<Integer> ans = new Vector<>(); // Iterate the given array for (int i = 0; i < n; i++) { count = 0; k = i + 1; temp = 0; // Traverse the k elements while (count < x) { temp += a.elementAt(k % n); count++; k++; } // Push the K elements sum ans.add(temp); } // Return the resultant vector return ans;}// Function that prints the sum of next// K element for each index in the arraystatic void sumOfKelements(Vector<Integer> arr, int K){ // Size of the array int N = (int)arr.size(); // Stores the result Vector<Integer> ans = new Vector<>(); // If key is negative, // reverse the array if (K < 0) { K = K * (-1); // Reverse the array arr = reverse(arr); // Find the resultant vector ans = sumOfKelementsUtil(arr, K); // Reverse the array again to // get the original sequence ans = reverse(ans); } // If K is positive else { ans = sumOfKelementsUtil(arr, K); } // Print the answer for (int i = 0; i < N; i++) { System.out.print(ans.elementAt(i) + " "); }}// Driver Codepublic static void main(String[] args){ // Given array arr[] Vector<Integer> arr = new Vector<>(); arr.add(4); arr.add(2); arr.add(-5); arr.add(11); int K = 3; // Function Call sumOfKelements(arr, K);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for # the above approach# Function to find the sum of next# or previous k array elementsdef sumOfKelementsUtil(a, x): # Size of the array n = len(a) # Stores the result ans = [] # Iterate the given array for i in range(n): count = 0 k = i + 1 temp = 0 # Traverse the k elements while (count < x): temp += a[k % n] count += 1 k += 1 # Push the K elements sum ans.append(temp) # Return the resultant vector return ans# Function that prints the # sum of next K element for # each index in the arraydef sumOfKelements(arr, K): # Size of the array N = len(arr) #Stores the result ans = [] # If key is negative, # reverse the array if (K < 0): K = K * (-1) # Reverse the array arr.reverse() # Find the resultant vector ans = sumOfKelementsUtil(arr, K) #Reverse the array again to # get the original sequence ans.reverse() # If K is positive else: ans = sumOfKelementsUtil(arr, K) # Print the answer for i in range(N): print (ans[i], end = " ") # Driver Codeif __name__ == "__main__": # Given array arr[] arr = [4, 2, -5, 11] K = 3 # Function Call sumOfKelements(arr, K)# This code is contributed by Chitranayal |
C#
// C# program for // the above approachusing System;using System.Collections.Generic;class GFG{ // Reverse arraystatic List<int> reverse(List<int> a) { int i, n = a.Count, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Function to find the sum of next// or previous k array elementsstatic List<int> sumOfKelementsUtil( List<int>a, int x){ // Size of the array int n = a.Count; int count, k, temp; // Stores the result List<int> ans = new List<int>(); // Iterate the given array for (int i = 0; i < n; i++) { count = 0; k = i + 1; temp = 0; // Traverse the k elements while (count < x) { temp += a[k % n]; count++; k++; } // Push the K elements sum ans.Add(temp); } // Return the resultant vector return ans;}// Function that prints the sum of next// K element for each index in the arraystatic void sumOfKelements(List<int> arr, int K){ // Size of the array int N = (int)arr.Count; // Stores the result List<int> ans = new List<int>(); // If key is negative, // reverse the array if (K < 0) { K = K * (-1); // Reverse the array arr = reverse(arr); // Find the resultant vector ans = sumOfKelementsUtil(arr, K); // Reverse the array again to // get the original sequence ans = reverse(ans); } // If K is positive else { ans = sumOfKelementsUtil(arr, K); } // Print the answer for (int i = 0; i < N; i++) { Console.Write(ans[i] + " "); }}// Driver Codepublic static void Main(String[] args){ // Given array []arr List<int> arr = new List<int>(); arr.Add(4); arr.Add(2); arr.Add(-5); arr.Add(11); int K = 3; // Function Call sumOfKelements(arr, K);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for the above approach // Function to print the // required resultant array function sumOfKElements( arr, n, k) { // Reverse the array let rev = false; if (k < 0) { rev = true; k *= -1; let l = 0, r = n - 1; // Traverse the range while (l < r) { let tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; } } // Store prefix sum let dp = Array.from({length: n}, (_, i) => 0); dp[0] = arr[0]; // Find the prefix sum for (let i = 1; i < n; i++) { dp[i] += dp[i - 1] + arr[i]; } // Store the answer let ans = Array.from({length: n}, (_, i) => 0); // Calculate the answers for (let i = 0; i < n; i++) { if (i + k < n) ans[i] = dp[i + k] - dp[i]; else { // Count of remaining elements let x = k - (n - 1 - i); // Add the sum of all elements // y times let y = Math.floor(x / n); // Add the remaining elements let rem = x % n; // Update ans[i] ans[i] = dp[n - 1] - dp[i] + y * dp[n - 1] + (rem - 1 >= 0 ? dp[rem - 1] : 0); } } // If array is reversed print // ans[] in reverse if (rev) { for (let i = n - 1; i >= 0; i--) { document.write(ans[i] + " "); } } else { for (let i = 0; i < n; i++) { document.write(ans[i] + " "); } } }// Driver Code // Given array arr[] let arr = [ 4, 2, -5, 11 ]; let N = arr.length; // Given K let K = 3; // Function sumOfKElements(arr, N, K);// This code is contributed by souravghosh0416.</script> |
Output
8 10 17 1
Time Complexity: O(N*K), where N is the length of the given array and K is the given integer.
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use prefix sum. Follow the steps below to solve the problem:
- If K is negative, reverse the given array and multiply K with -1.
- Compute and store the prefix sum of the given array in pre[].
- Create the array ans[] to store the answer for each element.
- For every index i, if i + K is smaller than N, then update ans[i] = pre[i + k] – pre[i]
- Otherwise, add the sum of all the elements from index i to N – 1, find remaining K – (N – 1 – i) elements because (N – 1 – i) elements are already added in the above step.
- Add the sum of all elements floor((K – N – 1 – i)/N) times and the sum of remaining elements of the given array from 0 to ((K – (N – 1 – i)) % N) – 1.
- After calculating the answer for each element of the array, check if the array was reversed previously. If yes, reverse the ans[] array.
- Print all the elements stored in the array ans[] after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to print the// required resultant arrayvoid sumOfKElements(int arr[], int n, int k){ // Reverse the array bool rev = false; if (k < 0) { rev = true; k *= -1; int l = 0, r = n - 1; // Traverse the range while (l < r) { int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; } } // Store prefix sum int dp[n] = {0}; dp[0] = arr[0]; // Find the prefix sum for(int i = 1; i < n; i++) { dp[i] += dp[i - 1] + arr[i]; } // Store the answer int ans[n] = {0}; // Calculate the answers for(int i = 0; i < n; i++) { if (i + k < n) ans[i] = dp[i + k] - dp[i]; else { // Count of remaining elements int x = k - (n - 1 - i); // Add the sum of all elements // y times int y = x / n; // Add the remaining elements int rem = x % n; // Update ans[i] ans[i] = dp[n - 1] - dp[i] + y * dp[n - 1] + (rem - 1 >= 0 ? dp[rem - 1] : 0); } } // If array is reversed print // ans[] in reverse if (rev) { for(int i = n - 1; i >= 0; i--) { cout << ans[i] << " "; } } else { for(int i = 0; i < n; i++) { cout << ans[i] << " "; } }}// Driver Codeint main(){ // Given array arr[] int arr[] = { 4, 2, -5, 11 }; int N = sizeof(arr) / sizeof(arr[0]); // Given K int K = 3; // Function sumOfKElements(arr, N, K);}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to print the // required resultant array static void sumOfKElements( int arr[], int n, int k) { // Reverse the array boolean rev = false; if (k < 0) { rev = true; k *= -1; int l = 0, r = n - 1; // Traverse the range while (l < r) { int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; } } // Store prefix sum int dp[] = new int[n]; dp[0] = arr[0]; // Find the prefix sum for (int i = 1; i < n; i++) { dp[i] += dp[i - 1] + arr[i]; } // Store the answer int ans[] = new int[n]; // Calculate the answers for (int i = 0; i < n; i++) { if (i + k < n) ans[i] = dp[i + k] - dp[i]; else { // Count of remaining elements int x = k - (n - 1 - i); // Add the sum of all elements // y times int y = x / n; // Add the remaining elements int rem = x % n; // Update ans[i] ans[i] = dp[n - 1] - dp[i] + y * dp[n - 1] + (rem - 1 >= 0 ? dp[rem - 1] : 0); } } // If array is reversed print // ans[] in reverse if (rev) { for (int i = n - 1; i >= 0; i--) { System.out.print(ans[i] + " "); } } else { for (int i = 0; i < n; i++) { System.out.print(ans[i] + " "); } } } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 4, 2, -5, 11 }; int N = arr.length; // Given K int K = 3; // Function sumOfKElements(arr, N, K); }} |
Python3
# Python3 program for # the above approach# Function to print# required resultant arraydef sumOfKElements(arr, n, k): # Reverse the array rev = False; if (k < 0): rev = True; k *= -1; l = 0; r = n - 1; # Traverse the range while (l < r): tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l += 1; r -= 1; # Store prefix sum dp = [0] * n; dp[0] = arr[0]; # Find the prefix sum for i in range(1, n): dp[i] += dp[i - 1] + arr[i]; # Store the answer ans = [0] * n; # Calculate the answers for i in range(n): if (i + k < n): ans[i] = dp[i + k] - dp[i]; else: # Count of remaining # elements x = k - (n - 1 - i); # Add the sum of # all elements y times y = x // n; # Add the remaining # elements rem = x % n; # Update ans[i] ans[i] = (dp[n - 1] - dp[i] + y * dp[n - 1] + (dp[rem - 1] if rem - 1 >= 0 else 0)); # If array is reversed # print ans in reverse if (rev): for i in range(n - 1, -1, -1): print(ans[i], end = " "); else: for i in range(n): print(ans[i], end = " ");# Driver Codeif __name__ == '__main__': # Given array arr arr = [4, 2, -5, 11]; N = len(arr); # Given K K = 3; # Function sumOfKElements(arr, N, K);# This code is contributed by 29AjayKumar |
C#
// C# program for // the above approachusing System;class GFG {// Function to print the// required resultant arraystatic void sumOfKElements(int []arr, int n, int k){ // Reverse the array bool rev = false; if (k < 0) { rev = true; k *= -1; int l = 0, r = n - 1; // Traverse the range while (l < r) { int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; } } // Store prefix sum int []dp = new int[n]; dp[0] = arr[0]; // Find the prefix sum for (int i = 1; i < n; i++) { dp[i] += dp[i - 1] + arr[i]; } // Store the answer int []ans = new int[n]; // Calculate the answers for (int i = 0; i < n; i++) { if (i + k < n) ans[i] = dp[i + k] - dp[i]; else { // Count of remaining elements int x = k - (n - 1 - i); // Add the sum of all elements // y times int y = x / n; // Add the remaining elements int rem = x % n; // Update ans[i] ans[i] = dp[n - 1] - dp[i] + y * dp[n - 1] + (rem - 1 >= 0 ? dp[rem - 1] : 0); } } // If array is reversed print // ans[] in reverse if (rev) { for (int i = n - 1; i >= 0; i--) { Console.Write(ans[i] + " "); } } else { for (int i = 0; i < n; i++) { Console.Write(ans[i] + " "); } }}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = {4, 2, -5, 11}; int N = arr.Length; // Given K int K = 3; // Function sumOfKElements(arr, N, K);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to print the// required resultant arrayfunction sumOfKElements(arr, n, k){ // Reverse the array let rev = false; if (k < 0) { rev = true; k *= -1; let l = 0, r = n - 1; // Traverse the range while (l < r) { let tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; } } // Store prefix sum let dp = new Uint8Array(n); dp[0] = arr[0]; // Find the prefix sum for(let i = 1; i < n; i++) { dp[i] += dp[i - 1] + arr[i]; } // Store the answer let ans = new Uint8Array(n); // Calculate the answers for(let i = 0; i < n; i++) { if (i + k < n) ans[i] = dp[i + k] - dp[i]; else { // Count of remaining elements let x = k - (n - 1 - i); // Add the sum of all elements // y times let y = Math.floor(x / n); // Add the remaining elements let rem = x % n; // Update ans[i] ans[i] = dp[n - 1] - dp[i] + y * dp[n - 1] + (rem - 1 >= 0 ? dp[rem - 1] : 0); } } // If array is reversed print // ans[] in reverse if (rev) { for(let i = n - 1; i >= 0; i--) { document.write(ans[i] + " "); } } else { for(let i = 0; i < n; i++) { document.write(ans[i] + " "); } }}// Driver Code // Given array arr[] let arr = [ 4, 2, -5, 11 ]; let N = arr.length; // Given K let K = 3; // Function sumOfKElements(arr, N, K);//This code is contributed by Mayank Tyagi</script> |
Output
8 10 17 1
Time Complexity: O(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!
