Hacer que los elementos de la array sean iguales en pasos mínimos

Dada una array de N elementos donde el primer elemento es un número positivo distinto de cero M , y el resto N – 1 elementos son 0, la tarea es calcular el número mínimo de pasos necesarios para que toda la array sea igual respetando lo siguiente reglas:
1. El i ^-ésimo elemento puede incrementarse en uno si y solo si el i-1- ^ésimo elemento es estrictamente mayor que el i-ésimo elemento 
2. Si el i ^-ésimo elemento se incrementa en uno, entonces el i+1 ^-ésimo no puede incrementarse al mismo tiempo. (es decir, los elementos consecutivos no se pueden aumentar al mismo tiempo) 
3. Se pueden incrementar varios elementos simultáneamente en un solo paso.
Ejemplos: 
 

Entrada: N = 3, M = 4 
Salida: 8 
Explicación:  la
array es 4 0 0 
En 4 pasos, el elemento en el índice 1 aumenta, por lo que la array se convierte en {4, 4, 0} . En los siguientes 4 pasos, el elemento en el índice 3 aumenta, por lo que la array se convierte en {4, 4, 4} 
Por lo tanto, se requieren 4 + 4 = 8 operaciones para hacer que todos los elementos de la array sean iguales
Entrada: N = 4, M = 4 
Salida: 9 
Explicación : 
Los pasos se muestran en el diagrama de flujo que se proporciona 
a continuación. Consulte el diagrama de flujo que se proporciona a continuación. 
 

Enfoque: 
Para maximizar la cantidad de incrementos por paso, se crea más cantidad de desequilibrios (array[i]>array[i+1]),
Paso 1 , elemento 0 > elemento 1, por lo que se incrementa el elemento 1, 
Paso 2 , elemento 1 > elemento 2 por lo que el elemento 2 se incrementa en 1
Paso 3 , elemento 0 > elemento 1 y elemento 2> elemento 3 por lo que los elementos 1 y 3 se incrementan en 1
Paso 4 , elemento 1 > elemento 2 elemento 3 > elemento 4 por lo que el elemento 2 y 4 se incrementan
Paso 5 , elemento 0> elemento 1; elemento 2>elemento 3; elemento 4> elemento 5; por lo que los elementos 1, 3 y 5 se incrementan. 
y así sucesivamente…
Considere la siguiente array, 
5 0 0 0 0 0
1)5 1 0 0 0 0 
2) 5 1 1 0 0 0 
3) 5 2 1 1 0 0 
4) 5 2 2 1 1 0 
5) 5 3 2 2 1 1 
6) 5 3 3 2 2 1 
7) 5 4 3 3 2 2 
8) 5 4 4 3 3 2 
9) 5 5 4 4 3 3 
10) 5 5 5 4 4 3 
11) 5 5 5 5 4 4 
12) 5 5 5 5 5 4 
13) 5 5 5 5 5 5
Tenga en cuenta que después de que se crea un desequilibrio (es decir, array[i]>array[i+1]), el elemento se incrementa en uno en pasos alternos. En el paso 1, el elemento 1 se incrementa a 1, en el paso 2, el elemento 2 se incrementa a 1, en el paso 3, el elemento 3 se incrementa a 1, por lo que en el paso n-1, el elemento n-1 ^se convertirá en 1. Después de eso, n- El 1.º ^elemento se incrementa en 1 en pasos alternos hasta que alcanza el valor en el elemento 0. Luego, toda la array se vuelve igual.
Entonces, el patrón seguido por el último elemento es 
(0, 0, 0 .., 0) hasta que (N – 4) ^el elemento se convierte en 1, que es n-4 pasos 
y después de eso, 
(0, 0, 1, 1, 2 , 2, 3, 3, 4, 4, … M – 1, M – 1, M) que es 2*m + 1 pasos .
Entonces, el resultado final se convierte en (N – 3) + 2 * M.
Hay algunos casos de esquina que deben manejarse, a saber. Cuando N = 1 , la array tiene un solo elemento, por lo que el número de pasos requeridos = 0. y Cuando N = 2 , el número de pasos requeridos es igual a M 
 

// C++ program to make the array elements equal in minimum steps
 
#include <bits/stdc++.h>
using namespace std;
 
// Returns the minimum steps required to make an array of N
// elements equal, where the first array element equals M
int steps(int N, int M)
{
    // Corner Case 1: When N = 1
    if (N == 1)
        return 0;
 
    // Corner Case 2: When N = 2
    else if (N == 2) // corner case 2
        return M;
 
    return 2 * M + (N - 3);
}
 
// Driver Code
int main()
{
    int N = 4, M = 4;
    cout << steps(N, M);
    return 0;
}

// Java program to make the array elements
// equal in minimum steps
 
import java.io.*;
 
class GFG {
 
    // Returns the minimum steps required
    // to make an array of N elements equal,
    // where the first array element equals M
    static int steps(int N, int M)
    {
        // Corner Case 1: When N = 1
        if (N == 1)
            return 0;
     
        // Corner Case 2: When N = 2
        else if (N == 2) // corner case 2
            return M;
     
        return 2 * M + (N - 3);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int N = 4, M = 4;
        System.out.print( steps(N, M));
    }
}
 
// This code is contributed by anuj_67.

# Python program to make
# the array elements equal
# in minimum steps
 
# Returns the minimum steps
# required to make an array
# of N elements equal, where
# the first array element
# equals M
def steps(N, M):
 
    # Corner Case 1: When N = 1
    if (N == 1):
        return 0
 
    # Corner Case 2: When N = 2
    elif(N == 2):
        return M
 
    return 2 * M + (N - 3)
 
# Driver Code
N = 4
M = 4
print(steps(N,M))
 
# This code is contributed
# by Shivi_Aggarwal.

// C# program to make the array
// elements equal in minimum steps
using System;
 
class GFG
{
 
    // Returns the minimum steps
    // required to make an array
    // of N elements equal, where
    // the first array element
    // equals M
    static int steps(int N, int M)
    {
        // Corner Case 1: When N = 1
        if (N == 1)
             return 0;
     
        // Corner Case 2: When N = 2
        else if (N == 2) // corner case 2
            return M;
     
        return 2 * M + (N - 3);
    }
     
    // Driver Code
    public static void Main ()
    {
        int N = 4, M = 4;
        Console.WriteLine(steps(N, M));
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to make the array
// elements equal in minimum steps
 
// Returns the minimum steps required
// to make an array of N elements equal,
// where the first array element equals M
function steps($N, $M)
{
    // Corner Case 1: When N = 1
    if ($N == 1)
        return 0;
 
    // Corner Case 2: When N = 2
    else if ($N == 2) // corner case 2
        return $M;
 
    return 2 * $M + ($N - 3);
}
 
// Driver Code
$N = 4;
$M = 4;
echo steps($N, $M);
     
// This code is contributed by ajit
?>

<script>
    // Javascript program to make the array
    // elements equal in minimum steps
     
    // Returns the minimum steps
    // required to make an array
    // of N elements equal, where
    // the first array element
    // equals M
    function steps(N, M)
    {
        // Corner Case 1: When N = 1
        if (N == 1)
             return 0;
       
        // Corner Case 2: When N = 2
        else if (N == 2) // corner case 2
            return M;
       
        return 2 * M + (N - 3);
    }
     
    let N = 4, M = 4;
      document.write(steps(N, M));
    
   // This code is contributed by suresh07.
</script>

9