Given a circular array arr[] of N integers and two integer M and K, the task is to find the sum of array elements arr[] after performing M operations such that in each operation, increment the adjacent array elements of all the positive array element by K, i.e., if arr[i] > 0, then increment the value of arr[i – 1] and arr[i + 1] by K.
Examples:
Input: arr[] = {0, 1, 0, 1, 0, 0}, M = 2, K = 1
Output: 16
Explanation:
In the 1st operation after incrementing the adjacent array elements of arr[] > 0, the given array modifies to arr[] = {1, 1, 2, 1, 1, 0}.
In the 2nd operation after incrementing the adjacent array elements of arr[] > 0, the given array modifies to arr[] = {2, 3, 4, 3, 2, 2}. So the sum of all elements of arr[] is 16.Input: arr[] = {1, 2, 3}, M = 10, K = 2
Output: 126
Approach: The given problem can be solved based on the following observations:
- Any non-zero element will always increase the sum of the array by 2 * K in a single move.
- The number of moves required to increment an integer from 0 to a non-zero value is always equal to the distance of the closest non-zero element.
Follow the below steps to solve the problem:
- Create an array steps[], which store the distance of the current element from the nearest non-zero element.
- Create a function nearestLeft() to find the index of the nearest non-zero element while traversing the array in the left direction using the approach discussed in this article.
- Similarly, create a function nearestRight() to find the index of the nearest non-zero element while traversing the array in the right direction.
- The number of operations required to increment the value of the ith element from 0 is given by steps[i] and after that, it will contribute 2 * K to the final sum after each operation. Therefore, the total contribution of ith integer in the final sum after M operations are 2 * K * (M – steps[i]).
- Traverse the array arr[] in the range [1, N] and keep track of the sum contributed by each index in a variable, say sum.
- After completing the above steps, print the value of sum as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the nearest non-zero// element in the left directionvoid nearestLeft(int arr[], int N, vector<int>& steps){ // Stores the index of the first element // greater than 0 from the right side int L = -N; // Traverse the array in the range [1, N] for (int i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = -(N - i); break; } } // Traverse the array from the left side for (int i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = i; } // Update the value of steps[i] steps[i] = i - L; }}// Function to find the nearest non-zero// element in the right directionvoid nearestRight(int arr[], int N, vector<int>& steps){ // Stores the index of the first element // greater than 0 from the left side int R = 2 * N; // Traverse the array from the left side for (int i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = N + i; break; } } // Traverse the array from the right side for (int i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = i; } // Update the value of steps[i] steps[i] = min(steps[i], R - i); }}// Function to find the sum of the array// after the given operation M timesint findSum(int arr[], int N, int M, int K){ // Stores the distance of the nearest // non zero element. vector<int> steps(N); // Stores sum of the initial array arr[] int sum = accumulate(arr, arr + N, 0); if (sum == 0) { return 0; } nearestLeft(arr, N, steps); nearestRight(arr, N, steps); // Traverse the array from the left side for (int i = 0; i < N; i++) // Update the value of sum sum += 2 * K * max(0, M - steps[i]); // Print the total sum of the array return sum;}// Driver Codeint main(){ int arr[] = { 0, 1, 0, 1, 0, 0 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 2; int K = 1; cout << findSum(arr, N, M, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the nearest non-zero// element in the left directionstatic void nearestLeft(int arr[], int N, int[] steps){ // Stores the index of the first element // greater than 0 from the right side int L = -N; // Traverse the array in the range [1, N] for (int i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = -(N - i); break; } } // Traverse the array from the left side for (int i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = i; } // Update the value of steps[i] steps[i] = i - L; }}// Function to find the nearest non-zero// element in the right directionstatic void nearestRight(int arr[], int N, int[] steps){ // Stores the index of the first element // greater than 0 from the left side int R = 2 * N; // Traverse the array from the left side for (int i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = N + i; break; } } // Traverse the array from the right side for (int i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = i; } // Update the value of steps[i] steps[i] = Math.min(steps[i], R - i); }}static int accumulate(int[] arr, int start, int end){ int sum = 0; for(int i= 0; i < arr.length; i++) sum += arr[i]; return sum;} // Function to find the sum of the array// after the given operation M timesstatic int findSum(int arr[], int N, int M, int K){ // Stores the distance of the nearest // non zero element. int []steps = new int[N]; // Stores sum of the initial array arr[] int sum = accumulate(arr, 0, N); if (sum == 0) { return 0; } nearestLeft(arr, N, steps); nearestRight(arr, N, steps); // Traverse the array from the left side for (int i = 0; i < N; i++) // Update the value of sum sum += 2 * K * Math.max(0, M - steps[i]); // Print the total sum of the array return sum;}// Driver Codepublic static void main(String[] args){ int arr[] = { 0, 1, 0, 1, 0, 0 }; int N = arr.length; int M = 2; int K = 1; System.out.print(findSum(arr, N, M, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to find the nearest non-zero# element in the left directiondef nearestLeft(arr, N, steps): # Stores the index of the first element # greater than 0 from the right side L = -N # Traverse the array in the range [1, N] for i in range(N - 1, -1, -1): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of L L = -(N - i) break # Traverse the array from the left side for i in range(N): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of L L = i # Update the value of steps[i] steps[i] = i - L# Function to find the nearest non-zero# element in the right directiondef nearestRight(arr, N, steps): # Stores the index of the first element # greater than 0 from the left side R = 2 * N # Traverse the array from the left side for i in range(N): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of R R = N + i break # Traverse the array from the right side for i in range(N - 1, -1, -1): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of R R = i # Update the value of steps[i] steps[i] = min(steps[i], R - i)# Function to find the sum of the array# after the given operation M timesdef findSum(arr, N, M, K): # Stores the distance of the nearest # non zero element. steps = [0] * N # Stores sum of the initial array arr[] s = sum(arr) if (s == 0): return 0 nearestLeft(arr, N, steps) nearestRight(arr, N, steps) # Traverse the array from the left side for i in range(N): # Update the value of sum s += 2 * K * max(0, M - steps[i]) # Print the total sum of the array return s# Driver Codeif __name__ == "__main__": arr = [ 0, 1, 0, 1, 0, 0 ] N = len(arr) M = 2 K = 1 print(findSum(arr, N, M, K))# This code is contributed by ukasp |
C#
// C# program for the above approachusing System;public class GFG{// Function to find the nearest non-zero// element in the left directionstatic void nearestLeft(int []arr, int N, int[] steps){ // Stores the index of the first element // greater than 0 from the right side int L = -N; // Traverse the array in the range [1, N] for (int i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = -(N - i); break; } } // Traverse the array from the left side for (int i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = i; } // Update the value of steps[i] steps[i] = i - L; }}// Function to find the nearest non-zero// element in the right directionstatic void nearestRight(int []arr, int N, int[] steps){ // Stores the index of the first element // greater than 0 from the left side int R = 2 * N; // Traverse the array from the left side for (int i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = N + i; break; } } // Traverse the array from the right side for (int i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = i; } // Update the value of steps[i] steps[i] = Math.Min(steps[i], R - i); }}static int accumulate(int[] arr, int start, int end){ int sum = 0; for(int i= 0; i < arr.Length; i++) sum += arr[i]; return sum;} // Function to find the sum of the array// after the given operation M timesstatic int findSum(int []arr, int N, int M, int K){ // Stores the distance of the nearest // non zero element. int []steps = new int[N]; // Stores sum of the initial array []arr int sum = accumulate(arr, 0, N); if (sum == 0) { return 0; } nearestLeft(arr, N, steps); nearestRight(arr, N, steps); // Traverse the array from the left side for (int i = 0; i < N; i++) // Update the value of sum sum += 2 * K * Math.Max(0, M - steps[i]); // Print the total sum of the array return sum;}// Driver Codepublic static void Main(String[] args){ int []arr = { 0, 1, 0, 1, 0, 0 }; int N = arr.Length; int M = 2; int K = 1; Console.Write(findSum(arr, N, M, K));}}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the nearest non-zero // element in the left direction function nearestLeft(arr, N, steps) { // Stores the index of the first element // greater than 0 from the right side let L = -N; // Traverse the array in the range [1, N] for (let i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = -(N - i); break; } } // Traverse the array from the left side for (let i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of L L = i; } // Update the value of steps[i] steps[i] = i - L; } } // Function to find the nearest non-zero // element in the right direction function nearestRight(arr, N, steps) { // Stores the index of the first element // greater than 0 from the left side let R = 2 * N; // Traverse the array from the left side for (let i = 0; i < N; i++) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = N + i; break; } } // Traverse the array from the right side for (let i = N - 1; i >= 0; i--) { // Check arr[i] is greater than 0 if (arr[i] > 0) { // Update the value of R R = i; } // Update the value of steps[i] steps[i] = Math.min(steps[i], R - i); } } // Function to find the sum of the array // after the given operation M times function findSum(arr, N, M, K) { // Stores the distance of the nearest // non zero element. let steps = new Array(N); // Stores sum of the initial array arr[] let sum = 0; for (let i = 0; i < N; i++) { sum = sum + arr[i]; } if (sum == 0) { return 0; } nearestLeft(arr, N, steps); nearestRight(arr, N, steps); // Traverse the array from the left side for (let i = 0; i < N; i++) // Update the value of sum sum += 2 * K * Math.max(0, M - steps[i]); // Print the total sum of the array return sum; } // Driver Code let arr = [0, 1, 0, 1, 0, 0]; let N = arr.length; let M = 2; let K = 1; document.write(findSum(arr, N, M, K)); // This code is contributed by Potta Lokesh </script> |
Output:
16
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!
Share your thoughts in the comments
