Given an array arr[] consisting of N integers, the task is to find the minimum number of operations required to make the array non-decreasing by choosing any subset of array arr[] and adding 2i to all elements of the subset in ith step.
Examples:
Input: arr[ ] = {1, 7, 6, 5}
Output: 2
Explanation:
One way to make the array non-decreasing is:
- Increment arr[1] and arr[3] by 20. Thereafter, the array modifies to {2, 7, 6, 6}.
- Increment arr[2] and arr[3] by 21. Thereafter, the array modifies to {2, 7, 8, 8}.
Therefore, two operations are needed to make the array non-decreasing. Also, it is the minimum count of operations.
Input: arr[ ] = {1, 2, 3, 4, 5}
Output: 0
Approach: The given problem can be solved based on the following observations:
Supposing A[] as the original array and B[] as the final, then:
- There will be only one way to make the final non-decreasing array, because there is no more than a single way to make a specific amount of addition to a number. Therefore, the task will be to minimize the max(B1?A1, B2?A2, …, Bn?An), as smaller differences lead to the use of shorter time to make the array non-decreasing.
- B[] is optimal when B[i] is the maximum value between B1, B2, …, B[i]?1 and A[i] because for each position i, B[i]?A[i] should be as small as possible and B[i-1] ? B[i] and A[i] ? B[i].
- If X operations are performed, then any array element can be increased by any integer in the range [0, 2X-1].
Follow the steps below to solve the problem:
- Initialize a variable, say val as 0, to store the maximum difference between the final array elements and the original array elements at the same indices.
- Initialize another variable, say mx as INT_MIN, to store the maximum of the prefix of the array.
- Traverse the array, arr[] using variable i and in each iteration update mx to max(mx, arr[i]) and val to max(val, mx – arr[i]).
- The highest power of 2, smaller than an integer, val, and then store it in a variable, say res.
- Finally, after completing the above steps, print the value of res as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the minimum number// of steps required to make arr non-// decreasingint countMinSteps(int arr[], int N){ // Stores differences int val = 0; // Stores the max number int mx = INT_MIN; // Traverse the array arr[] for (int i = 0; i < N; i++) { int curr = arr[i]; // Update mx mx = max(mx, curr); // Update val val = max(val, mx - curr); } // Stores the result long long res = 0; // Iterate until 2^res-1 is less // than val while ((1LL << res) - 1 < val) { ++res; } // Return the answer return res;}// Driver Codeint main(){ // Given input int arr[] = { 1, 7, 6, 5 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << countMinSteps(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to count the minimum number // of steps required to make arr non- // decreasing static int countMinSteps(int arr[], int N) { // Stores differences int val = 0; // Stores the max number int mx = Integer.MIN_VALUE; // Traverse the array arr[] for (int i = 0; i < N; i++) { int curr = arr[i]; // Update mx mx = Math.max(mx, curr); // Update val val = Math.max(val, mx - curr); } // Stores the result long res = 0; // Iterate until 2^res-1 is less // than val while ((1 << res) - 1 < val) { ++res; } // Return the answer return (int)res; } // Driver Code public static void main(String[] args) { // Given input int arr[] = { 1, 7, 6, 5 }; int N = arr.length; // Function call System.out.println(countMinSteps(arr, N)); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach# Function to count the minimum number# of steps required to make arr non-# decreasingdef countMinSteps(arr, N): # Stores differences val = 0 # Stores the max number mx = -10**9 # Traverse the array arr[] for i in range(N): curr = arr[i] # Update mx mx = max(mx, curr) # Update val val = max(val, mx - curr) # Stores the result res = 0 # Iterate until 2^res-1 is less # than val while ((1 << res) - 1 < val): res += 1 # Return the answer return res# Driver Codeif __name__ == '__main__': # Given input arr = [ 1, 7, 6, 5 ] N = len(arr) # Function call print(countMinSteps(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the minimum number// of steps required to make arr non-// decreasingstatic int countMinSteps(int []arr, int N){ // Stores differences int val = 0; // Stores the max number int mx = Int32.MinValue; // Traverse the array arr[] for (int i = 0; i < N; i++) { int curr = arr[i]; // Update mx mx = Math.Max(mx, curr); // Update val val = Math.Max(val, mx - curr); } // Stores the result int res = 0; // Iterate until 2^res-1 is less // than val while ((1 << res) - 1 < val) { ++res; } // Return the answer return res;}// Driver Codepublic static void Main(){ // Given input int []arr = { 1, 7, 6, 5 }; int N = arr.Length; // Function call Console.Write(countMinSteps(arr, N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// JavaScript program for the above approach// Function to count the minimum number// of steps required to make arr non-// decreasingfunction countMinSteps(arr, N) { // Stores differences let val = 0; // Stores the max number let mx = Number.MIN_SAFE_INTEGER; // Traverse the array arr[] for (let i = 0; i < N; i++) { let curr = arr[i]; // Update mx mx = Math.max(mx, curr); // Update val val = Math.max(val, mx - curr); } // Stores the result let res = 0; // Iterate until 2^res-1 is less // than val while ((1 << res) - 1 < val) { ++res; } // Return the answer return res;}// Driver Code// Given inputlet arr = [1, 7, 6, 5];let N = arr.length;// Function calldocument.write(countMinSteps(arr, N));</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
