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

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 ^{i}**

^{ }to all elements of the subset in

**i**step.

^{th}**Examples:**

Input:arr[ ] = {1, 7, 6, 5}Output:2Explanation:

One way to make the array non-decreasing is:

- Increment arr[1] and arr[3] by 2
^{0}. Thereafter, the array modifies to {2, 7, 6, 6}.- Increment arr[2] and arr[3] by 2
^{1}. 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 andB[]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, as smaller differences lead to the use of shorter time to make the array non-decreasing._{2}−A_{2}, …, B_{n}−A_{n})B[]is optimal whenB[i]is the maximum value betweenBand_{1}, B_{2}, …, B[i]−1A[i]because for each positioni,B[i]−A[i]should be as small as possible andB[i-1] ≤ B[i]andA[i] ≤ B[i].- If
Xoperations 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**

2

**Time Complexity:** O(N)**Auxiliary Space: **O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.