Número mínimo de operaciones requeridas para hacer que una array no disminuya agregando 2^i a un subconjunto en cada i-ésima operación

Dada una array arr[] que consta de N enteros, la tarea es encontrar el número mínimo de operaciones requeridas para que la array no sea decreciente eligiendo cualquier subconjunto de la array arr[] y agregando 2 ⁱ a todos los elementos del subconjunto en i ^th paso.

Ejemplos:

Entrada: arr[ ] = {1, 7, 6, 5}
Salida: 2
Explicación:
una forma de hacer que la array no sea decreciente es:

1. Incremente arr[1] y arr[3] en 2 ⁰ . A partir de entonces, la array se modifica a {2, 7, 6, 6}.
2. Incremente arr[2] y arr[3] en 2 ¹ . A partir de entonces, la array se modifica a {2, 7, 8, 8}.

Por lo tanto, se necesitan dos operaciones para que la array no sea decreciente. Además, es el recuento mínimo de operaciones.

Entrada: arr[ ] = {1, 2, 3, 4, 5}
Salida: 0

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

Suponiendo que A[] es el arreglo original y B[] el final, entonces:

1. Solo habrá una forma de hacer la array final no decreciente, porque no hay más que una sola forma de hacer una cantidad específica de adición a un número. Por lo tanto, la tarea será minimizar el max(B1−A1 , B ₂ −A ₂ , …, B _n −A _n ) , ya que las diferencias más pequeñas conducen al uso de un tiempo más corto para hacer que la array no disminuya.
2.  B[] es óptimo cuando B[i] es el valor máximo entre B ₁ , B ₂ , …, B[i]−1 y A[i] porque para cada posición i ,   B[i]−A[i] debería ser lo más pequeño posible y B[i-1] ≤ B[i] y A[i] ≤ B[i] .
3. Si se realizan operaciones X , cualquier elemento de la array se puede aumentar en cualquier número entero en el rango [0, 2 ^X -1].

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos val as 0 , para almacenar la diferencia máxima entre los elementos de la array final y los elementos de la array original en los mismos índices.
• Inicialice otra variable, digamos mx como INT_MIN, para almacenar el máximo del prefijo de la array.
• Recorra la array , arr[] usando la variable i y en cada iteración actualice mx a max(mx, arr[i]) y val a max(val, mx – arr[i]) .
• La potencia más alta de 2, más pequeña que un número entero , val, y luego almacenarla en una variable, digamos res .
• Finalmente, después de completar los pasos anteriores, imprima el valor de res como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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.

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

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)