Minimum number of operations required to make an array non-decreasing by adding 2^i to a subset in every i-th operation

0 0 5 minutes read

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 2ⁱto all elements of the subset in i^th 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 2⁰. Thereafter, the array modifies to {2, 7, 6, 6}.

Increment arr[2] and arr[3] by 2¹. 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, B₂?A₂, …, B_n?A_n), 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 B₁, B₂, …, 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, 2^X-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-
// decreasing
int 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 Code
int 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 approach
import 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-
# decreasing
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
 
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 = 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 Code
public 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-
// decreasing
function 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 input
let arr = [1, 7, 6, 5];
let N = arr.length;
 
// Function call
 
document.write(countMinSteps(arr, N));
 
</script>

Output

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 zambiatek!