Given an array arr[] and an integer K, the task is to find the minimum number of operations required to change an array B of size N containing all zeros such that every element of B is greater than or equal to arr. i.e., arr[i] >= B[i]. In any operation, you can choose a subarray of B of size K and increment all the elements of the subarray by 1.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 2
Output: 9
Explanation:
At first B[] = {0, 0, 0, 0, 0} operations = 0
Increment subarray a[1:2] by 1 => B = {1, 1, 0, 0, 0}, operations = 1
Increment subarray a[2:3] by 1 => B = {1, 2, 1, 0, 0}, operations = 2
Increment subarray a[3:4] by 2 => B = {1, 2, 3, 2, 0}, operations = 4
Increment subarray a[4:5] by 5 => B = {1, 2, 3, 7, 5}, operations = 9
Therefore, count of such operations required is 9.Input: arr[] = {2, 3, 1}, K = 3
Output: 3
Explanation:
Incrementing the entire array by 3
Approach: The idea is to increment the subarray of size K whenever there is a B[i] is less than arr[i] and also increment the count of such operations by 1 at each step. To increment the subarray of size K use the Difference array for Range Query update in O(1).
Below is the implementation of the above approach:
C++
// C++ implementation to find the // minimum number of operations // required to change an array of// all zeros such that every element// is greater than the given array#include <bits/stdc++.h>using namespace std;// Function to find the minimum // number of operations required// to change all the array of zeros// such that every element is greater// than the given arrayint find_minimum_operations(int n, int b[], int k){ // Declaring the difference // array of size N int d[n + 1] = {0}; // Number of operations int operations = 0, need; for(int i = 0; i < n; i++) { // First update the D[i] value // with the previous value if (i > 0) { d[i] += d[i - 1]; } // The index i has to be incremented if (b[i] > d[i]) { // We have to perform // (b[i]-d[i]) operations more operations += b[i] - d[i]; need = b[i] - d[i]; // Increment the range // i to i + k by need d[i] += need; // Check if i + k is valid index if(i + k <= n) { d[i + k]-= need; } } } cout << operations << endl;}// Driver Codeint main(){ int n = 5; int b[] = { 1, 2, 3, 4, 5 }; int k = 2; // Function Call find_minimum_operations(n, b, k); return 0;}// This code is contributed by shubhamsingh10 |
Java
// Java implementation to find the // minimum number of operations // required to change an array of// all zeros such that every element// is greater than the given arrayclass GFG{// Function to find the minimum // number of operations required// to change all the array of zeros// such that every element is greater// than the given arraystatic void find_minimum_operations(int n, int b[], int k){ // Declaring the difference // array of size N int d[] = new int[n + 1]; // Number of operations int i, operations = 0, need; for(i = 0; i < n; i++) { // First update the D[i] value // with the previous value if (i > 0) { d[i] += d[i - 1]; } // The index i has to be incremented if (b[i] > d[i]) { // We have to perform // (b[i]-d[i]) operations more operations += b[i] - d[i]; need = b[i] - d[i]; // Increment the range // i to i + k by need d[i] += need; // Check if i + k is valid index if(i + k <= n) { d[i + k]-= need; } } } System.out.println(operations);}// Driver Codepublic static void main (String []args){ int n = 5; int b[] = { 1, 2, 3, 4, 5 }; int k = 2; // Function Call find_minimum_operations(n, b, k);}}// This code is contributed by chitranayal |
Python3
# Python3 implementation to find the # minimum number of operations required # to change an array of all zeros # such that every element is greater than# the given array# Function to find the minimum # number of operations required# to change all the array of zeros# such that every element is greater# than the given arraydef find_minimum_operations(n, b, k): # Declaring the difference # array of size N d =[0 for i in range(n + 1)] # Number of operations operations = 0 for i in range(n): # First update the D[i] value with # the previous value d[i]+= d[i-1] # The index i has to be incremented if b[i]>d[i]: # We have to perform # (b[i]-d[i]) operations more operations+=(b[i]-d[i]) need =(b[i]-d[i]) # Increment the range # i to i + k by need d[i]+= need # Check if i + k is valid index if i + k<= n: d[i + k]-= need return operations# Driver Codeif __name__ == "__main__": n = 5 b =[1, 2, 3, 4, 5] k = 2 # Function Call print(find_minimum_operations(n, b, k)) |
C#
// C# implementation to find the // minimum number of operations // required to change an array of// all zeros such that every element// is greater than the given arrayusing System;class GFG{ // Function to find the minimum // number of operations required// to change all the array of zeros// such that every element is greater// than the given arraystatic void find_minimum_operations(int n, int[] b, int k){ // Declaring the difference // array of size N int[] d = new int[n + 1]; // Number of operations int i, operations = 0, need; for(i = 0; i < n; i++) { // First update the D[i] value // with the previous value if (i > 0) { d[i] += d[i - 1]; } // The index i has to be incremented if (b[i] > d[i]) { // We have to perform // (b[i]-d[i]) operations more operations += b[i] - d[i]; need = b[i] - d[i]; // Increment the range // i to i + k by need d[i] += need; // Check if i + k is valid index if(i + k <= n) { d[i + k]-= need; } } } Console.Write(operations);} // Driver Codepublic static void Main (string []args){ int n = 5; int[] b = { 1, 2, 3, 4, 5 }; int k = 2; // Function Call find_minimum_operations(n, b, k);}} // This code is contributed by rock_cool |
Javascript
<script>// Javascript implementation to find the// minimum number of operations// required to change an array of// all zeros such that every element// is greater than the given array// Function to find the minimum// number of operations required// to change all the array of zeros// such that every element is greater// than the given arrayfunction find_minimum_operations(n, b, k){ // Declaring the difference // array of size N let d = new Array(n + 1); d.fill(0); // Number of operations let i, operations = 0, need; for(i = 0; i < n; i++) { // First update the D[i] value // with the previous value if (i > 0) { d[i] += d[i - 1]; } // The index i has to be incremented if (b[i] > d[i]) { // We have to perform // (b[i]-d[i]) operations more operations += b[i] - d[i]; need = b[i] - d[i]; // Increment the range // i to i + k by need d[i] += need; // Check if i + k is valid index if (i + k <= n) { d[i + k]-= need; } } } document.write(operations);}// Driver codelet n = 5;let b = [ 1, 2, 3, 4, 5 ];let k = 2; // Function Callfind_minimum_operations(n, b, k);// This code is contributed by divyesh072019</script> |
Output:
9
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!
