Haga que todos los elementos de la array sean iguales a K incrementando repetidamente las subsecuencias

Dada una array arr[] que consta de N enteros y un entero K , la tarea es hacer que todos los elementos de la array sean iguales a K incrementando repetidamente todos los elementos de las subsecuencias en 1 . 
Nota: El valor de K es al menos el elemento máximo de la array .

Ejemplos:

Entrada: arr[] = {2, 3, 3, 4}, K = 5
Salida: 4 
Explicación:  
Operación 1: Seleccione la subsecuencia {2, 3, 4}. Después de incrementar cada elemento, la subsecuencia se modifica a {3, 4, 5}. La array se modifica a {3, 3, 4, 5}. 
Operación 2: Seleccione la subsecuencia {3, 4}. Después de incrementar cada elemento, la subsecuencia se modifica a {4, 5}. La array se modifica a {3, 4, 5, 5}. 
Operación 3: Seleccione la subsecuencia {3, 4}. Después de incrementar cada elemento, la subsecuencia se modifica a {4, 5}. La array se modifica a {4, 5, 5, 5}. 
Operación 4: Seleccione la subsecuencia {4}. Después de incrementar cada elemento, la subsecuencia se modifica a {5}. La array se modifica a {5, 5, 5, 5}.
 

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

Enfoque: La idea es usar Hashing para realizar un seguimiento de los elementos en las subsecuencias. Cuando un elemento en una subsecuencia aumenta en 1 , su frecuencia se reduce en 1 y la frecuencia de su valor modificado aumenta en 1 . 
Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , que almacene el número mínimo de operaciones requeridas.
• Inicialice un Hashmap , digamos mp , y almacene la frecuencia de los elementos del arreglo .
• Mientras que la frecuencia de K es menor que N , es decir, mp[K] < N , realice las siguientes operaciones:
  • Iterar a través de un rango [1, K – 1] usando la variable i
    • Si mp[i] es mayor que 0 , disminuya la frecuencia del valor actual y aumente la frecuencia de los siguientes elementos del grupo (i + 1) en 1 .
    • Si (i + 1) no forma parte de ningún valor anterior, sáltelo y continúe recorriendo el bucle .
  • Incremente el valor de ans en 1.
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

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 operations required to make all
// elements equal to k
void minOperations(int arr[], int n, int k)
{
    // Initialize a hashmap
    map<int, int> mp;
 
    // Store frequency of array elements
    for (int i = 0; i < n; i++) {
        mp[arr[i]]++;
    }
 
    // Store the minimum number of
    // operations required
    int ans = 0;
 
    // Iterate until all array elements
    // becomes equal to K
    while (mp[k] < n) {
 
        // Iterate through range [1, k - 1]
        // since only one element can be
        // increased from each group
        for (int i = 1; i <= k - 1; i++) {
 
            // Check if the current number
            // has frequency > 0, i.e.,
            // it is a part of a group
            if (mp[i]) {
 
                // If true, decrease the
                // frequency of current
                // group of element by 1
                mp[i]--;
 
                // Increase the frequency
                // of the next group of
                // elements by 1
                mp[i + 1]++;
 
                // If the next element is
                // not the part of any
                // group, then skip it
                if (mp[i + 1] == 1) {
                    i++;
                }
            }
        }
 
        // Increment count of operations
        ans++;
    }
 
    // Print the count of operations
    cout << ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 3, 4 };
    int K = 5;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    minOperations(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
  // Function to find the minimum number
  // of operations required to make all
  // elements equal to k
  static void minOperations(int arr[], int n, int k)
  {
 
    // Initialize a hashmap
    Map<Integer, Integer> mp = new HashMap<>();
 
    // Store frequency of array elements
    for (int i = 0; i < n; i++)
    {
      if (mp.containsKey(arr[i]))
      {
        mp.put(arr[i], mp.get(arr[i]) + 1);
      }
      else
      {
        mp.put(arr[i], 1);
      }
    }
 
    // Store the minimum number of
    // operations required
    int ans = 0;
 
    // Iterate until all array elements
    // becomes equal to K
    while (mp.containsKey(k) == false
           || mp.get(k) < n) {
 
      // Iterate through range [1, k - 1]
      // since only one element can be
      // increased from each group
      for (int i = 1; i <= k - 1; i++) {
 
        // Check if the current number
        // has frequency > 0, i.e.,
        // it is a part of a group
        if (mp.containsKey(i) && mp.get(i) > 0) {
 
          // If true, decrease the
          // frequency of current
          // group of element by 1
          mp.put(i, mp.get(i) - 1);
 
          // Increase the frequency
          // of the next group of
          // elements by 1
          if (mp.containsKey(i + 1))
            mp.put(i + 1, mp.get(i + 1) + 1);
          else
            mp.put(i + 1, 1);
 
          // If the next element is
          // not the part of any
          // group, then skip it
          if (mp.containsKey(i + 1)
              && mp.get(i + 1) == 1) {
            i++;
          }
        }
      }
 
      // Increment count of operations
      ans++;
    }
 
    // Print the count of operations
    System.out.print(ans);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 2, 3, 3, 4 };
    int K = 5;
    int N = arr.length;
 
    // Function Call
    minOperations(arr, N, K);
  }
}
 
// This code is contributed by Dharanendra L V.

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to find the minimum number
  // of operations required to make all
  // elements equal to k
  static void minOperations(int []arr, int n, int k)
  {
 
    // Initialize a hashmap
    Dictionary<int, int> mp = new Dictionary<int, int>();
 
    // Store frequency of array elements
    for (int i = 0; i < n; i++)
    {
      if (mp.ContainsKey(arr[i]))
      {
        mp[arr[i]] =  mp[arr[i]] + 1;
      }
      else
      {
        mp.Add(arr[i], 1);
      }
    }
 
    // Store the minimum number of
    // operations required
    int ans = 0;
 
    // Iterate until all array elements
    // becomes equal to K
    while (mp.ContainsKey(k) == false
           || mp[k] < n) {
 
      // Iterate through range [1, k - 1]
      // since only one element can be
      // increased from each group
      for (int i = 1; i <= k - 1; i++) {
 
        // Check if the current number
        // has frequency > 0, i.e.,
        // it is a part of a group
        if (mp.ContainsKey(i) && mp[i] > 0) {
 
          // If true, decrease the
          // frequency of current
          // group of element by 1
          mp[i] = mp[i] - 1;
 
          // Increase the frequency
          // of the next group of
          // elements by 1
          if (mp.ContainsKey(i + 1))
            mp[i + 1] = mp[i + 1] + 1;
          else
            mp.Add(i + 1, 1);
 
          // If the next element is
          // not the part of any
          // group, then skip it
          if (mp.ContainsKey(i + 1)
              && mp[i + 1] == 1) {
            i++;
          }
        }
      }
 
      // Increment count of operations
      ans++;
    }
 
    // Print the count of operations
    Console.Write(ans);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []arr = { 2, 3, 3, 4 };
    int K = 5;
    int N = arr.Length;
 
    // Function Call
    minOperations(arr, N, K);
  }
}
 
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program for the above approach
 
  // Function to find the minimum number
  // of operations required to make all
  // elements equal to k
  function minOperations(arr, n, k)
  {
  
    // Initialize a hashmap
    let mp = new Map();
  
    // Store frequency of array elements
    for (let i = 0; i < n; i++)
    {
      if (mp.has(arr[i]))
      {
        mp.set(arr[i], mp.get(arr[i]) + 1);
      }
      else
      {
        mp.set(arr[i], 1);
      }
    }
  
    // Store the minimum number of
    // operations required
    let ans = 0;
  
    // Iterate until all array elements
    // becomes equal to K
    while (mp.has(k) == false
           || mp.get(k) < n) {
  
      // Iterate through range [1, k - 1]
      // since only one element can be
      // increased from each group
      for (let i = 1; i <= k - 1; i++) {
  
        // Check if the current number
        // has frequency > 0, i.e.,
        // it is a part of a group
        if (mp.has(i) && mp.get(i) > 0) {
  
          // If true, decrease the
          // frequency of current
          // group of element by 1
          mp.set(i, mp.get(i) - 1);
  
          // Increase the frequency
          // of the next group of
          // elements by 1
          if (mp.has(i + 1))
            mp.set(i + 1, mp.get(i + 1) + 1);
          else
            mp.set(i + 1, 1);
  
          // If the next element is
          // not the part of any
          // group, then skip it
          if (mp.has(i + 1)
              && mp.get(i + 1) == 1) {
            i++;
          }
        }
      }
  
      // Increment count of operations
      ans++;
    }
  
    // Print the count of operations
    document.write(ans);
  }
 
// Driver Code
 
     let arr = [ 2, 3, 3, 4 ];
    let K = 5;
    let N = arr.length;
  
    // Function Call
    minOperations(arr, N, K);
 
</script>  

4

Complejidad temporal: O(N*K)
Espacio auxiliar: O(N)