Pasos mínimos para cambiar arr[K] a 0 disminuyendo arr[0] y cambiando para terminar repetidamente

Dada una array arr[] de tamaño N y un número entero que representa un índice K, la tarea es encontrar el número mínimo de operaciones en las que arr[K] se convierte en 0. En una operación, el valor del primer elemento de la array disminuye en 1 y va al final de la array. Si en algún momento, arr[i] se convierte en 0, entonces se elimina de la array y las operaciones se realizan en los elementos restantes.

Ejemplos:

Entrada:  arr[] = {2, 3, 2}, K = 2
Salida: 6
Explicación: Para la primera entrada,  
después de la iteración-1, la array cambia a [1, 2, 1]. Pasos tomados = 3 pasos
Después de la iteración 2, la array cambia a [0, 1, 0]. Pasos dados = 3 pasos
Por lo tanto, para el elemento en el índice 2, se necesitaron 6 pasos para convertirse en 0.

Entrada:  arr[] = {5, 1, 1, 1}, K = 0
Salida: 8

Enfoque: la idea es seguir recorriendo la array y disminuir el valor de arr[i] cuando es mayor que 0 y calcular la respuesta. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable tiempo como 0 para almacenar la respuesta.
• Atraviese un ciclo while hasta que arr[k] no sea 0 y realice las siguientes tareas:
  • Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
    • Si arr[i] es mayor que 0, reduzca el valor de arr[i] en 1, luego aumente el valor de time en 1.
    • Si arr[k] se convierte en 0, entonces se rompe.
• Después de realizar los pasos anteriores, imprima el valor del tiempo 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 find the minimum number
// of steps
void findMinimumNumberOfSteps(vector<int> arr,
                              int K)
{
 
    // Variable to store the answer
    int time = 0;
 
    // Traverse in the while loop
    while (arr[K] != 0) {
 
        // Iterate over the loop
        for (int i = 0; i < arr.size(); i++) {
 
            // Check the condition and
            // decrease the value
            if (arr[i] > 0) {
                arr[i] -= 1;
                time++;
            }
 
            // Break the loop
            if (arr[K] == 0)
                break;
        }
    }
 
    // Print the result
    cout << time;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 3, 2 };
    int K = 2;
    findMinimumNumberOfSteps(arr, K);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the minimum number
  // of steps
  static void findMinimumNumberOfSteps(int arr[],
                                       int K)
  {
 
    // Variable to store the answer
    int time = 0;
 
    // Traverse in the while loop
    while (arr[K] != 0) {
 
      // Iterate over the loop
      for (int i = 0; i < arr.length; i++) {
 
        // Check the condition and
        // decrease the value
        if (arr[i] > 0) {
          arr[i] -= 1;
          time++;
        }
 
        // Break the loop
        if (arr[K] == 0)
          break;
      }
    }
 
    // Print the result
    System.out.println(time);
  }
 
  // Driver Code
  public static void main (String[] args) {
    int arr[] = { 2, 3, 2 };
    int K = 2;
    findMinimumNumberOfSteps(arr, K);
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program to implement
# the above approach
 
# Function to find the minimum number
# of steps
def findMinimumNumberOfSteps(arr, K) :
 
    # Variable to store the answer
    time = 0
 
    # Traverse in the while loop
    while (arr[K] != 0) :
 
        # Iterate over the loop
        for i in range(0, len(arr)) :
             
            # Check the condition and
            # decrease the value
            if (arr[i] > 0) :
                arr[i] -= 1
                time += 1
             
 
            # Break the loop
            if (arr[K] == 0):
                break
 
    # Print the result
    print(time)
 
# Driver Code
arr = [ 2, 3, 2 ]
K = 2
findMinimumNumberOfSteps(arr, K)
 
# This code is contributed by sanjoy_62.

// C# program for the above approach
using System;
class GFG {
 
  // Function to find the minimum number
  // of steps
  static void findMinimumNumberOfSteps(int []arr,
                                       int K)
  {
 
    // Variable to store the answer
    int time = 0;
 
    // Traverse in the while loop
    while (arr[K] != 0) {
 
      // Iterate over the loop
      for (int i = 0; i < arr.Length; i++) {
 
        // Check the condition and
        // decrease the value
        if (arr[i] > 0) {
          arr[i] -= 1;
          time++;
        }
 
        // Break the loop
        if (arr[K] == 0)
          break;
      }
    }
 
    // Print the result
    Console.WriteLine(time);
  }
 
  // Driver Code
  public static void Main () {
    int []arr = { 2, 3, 2 };
    int K = 2;
    findMinimumNumberOfSteps(arr, K);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find the minimum number
       // of steps
       function findMinimumNumberOfSteps(arr,
           K) {
 
           // Variable to store the answer
           let time = 0;
 
           // Traverse in the while loop
           while (arr[K] != 0) {
 
               // Iterate over the loop
               for (let i = 0; i < arr.length; i++) {
 
                   // Check the condition and
                   // decrease the value
                   if (arr[i] > 0) {
                       arr[i] -= 1;
                       time++;
                   }
 
                   // Break the loop
                   if (arr[K] == 0)
                       break;
               }
           }
 
           // Print the result
           document.write(time);
       }
 
       // Driver Code
 
       let arr = [2, 3, 2];
       let K = 2;
       findMinimumNumberOfSteps(arr, K);
 
 
      // This code is contributed by Potta Lokesh
   </script>

6

Complejidad de tiempo: O(N*X), donde X es el valor de arr[K]
Espacio auxiliar: O(1)