Imprima la array lexicográficamente más pequeña reduciendo K a 0 en un número mínimo de operaciones

Dada una array arr[] y un entero K,  la tarea es reducir el valor de K a 0 realizando las siguientes operaciones. Una operación se define como elegir 2 índices i, j y restar el mínimo de arr[i] y K (es decir, X = min(arr[i], K) de arr[i] (es decir, arr[i] = arr [i] – X) y agregando el valor mínimo a arr[j] (arr[j] = arr[j] + X) e imprima la array lexicográficamente más pequeña . Tenga en cuenta que los elementos de la array arr[] no pueden ser negativos .

Ejemplos:

Entrada: N = 4, K = 2, arr[] = {4, 3, 2, 1}  
Salida: 2 2 3 3 
Explicación: 
Operación 1: Seleccione los índices 0 y 3, luego reste min de arr[0](= 4) y K(=2) de arr[0] y agregue el valor mínimo, es decir, K(=2) en arr[3](=1). Ahora, la array modificada es {2, 3, 2, 3}
Ahora, ordene la array modificada e imprímala.

Entrada: N = 3, K = 15, arr[] = {1, 2, 3}  
Salida: 0 0 6
Explicación: 
Operación 1: Seleccione los índices 0 y 2, luego reste min de arr[0](=1) y K(=15) de arr[0] y agregue el valor mínimo, es decir, arr[0](=1) en arr[2](=3). Ahora la array modificada es {0, 2, 4}.
Operación 2: seleccione los índices 1 y 2, luego reste el mínimo de arr[1](=2) y K(=15) de arr[1] y agregue el valor mínimo, es decir, arr[1](=2) en arr[2 ](=4).Ahora la array modificada es {0, 0, 6}.
Ahora, ordene la array modificada e imprímala.

Enfoque: este problema se puede resolver iterando sobre la array arr[] . Siga los pasos a continuación para resolver el problema:

• Iterar sobre el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
  • Si arr[i] es menor que K, siga los siguientes pasos.
  • Reste arr[i] de la variable K, sume el valor de arr[i] a arr[n-1] y establezca el valor de arr[i] en 0.
  • De lo contrario, reste K del valor de arr[i], agregue el valor de K a arr[n-1] y establezca el valor de K en 0 y rompa el bucle.
• Ordene la array arr[] .
• Después de realizar los pasos anteriores, imprima los elementos de la array arr[] .

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 resultant array.
void solve(int n, int k, int arr[])
{
 
    for (int i = 0; i < n - 1; i++) {
 
        // checking if aith value less than K
 
        if (arr[i] < k)
 
        {
            // subtracting ai value from K
            k = k - arr[i];
 
            // Adding ai value to an-1
            arr[n - 1]
                = arr[n - 1]
                  + arr[i];
 
            arr[i] = 0;
        }
 
        // if arr[i] value is greater than  K
        else {
 
            arr[i] = arr[i] - k;
            arr[n - 1] = arr[n - 1] + k;
            k = 0;
        }
    }
 
    // sorting the given array
    // to know about this function
    // check gfg stl sorting article
    sort(arr, arr + n);
 
    // Displaying the final array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
 
    int N = 6;
    int K = 2;
    int arr[N] = { 3, 1, 4, 6, 2, 5 };
 
    solve(N, K, arr);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG
{
   
  // Function to find the resultant array.
static void solve(int n, int k, int arr[])
{
 
    for (int i = 0; i < n - 1; i++) {
 
        // checking if aith value less than K
        if (arr[i] < k)
 
        {
           
            // subtracting ai value from K
            k = k - arr[i];
 
            // Adding ai value to an-1
            arr[n - 1]
                = arr[n - 1]
                  + arr[i];
 
            arr[i] = 0;
        }
 
        // if arr[i] value is greater than  K
        else {
 
            arr[i] = arr[i] - k;
            arr[n - 1] = arr[n - 1] + k;
            k = 0;
        }
    }
 
    // sorting the given array
    // to know about this function
    // check gfg stl sorting article
    Arrays.sort(arr);
 
    // Displaying the final array
    for (int i = 0; i < n; i++)
        System.out.print( arr[i] + " ");
}
 
// Driver code
    public static void main (String[] args) {
         int N = 6;
    int K = 2;
    int arr[] = { 3, 1, 4, 6, 2, 5 };
 
    solve(N, K, arr);
    }
}
 
// This code is contributed by Potta Lokesh

# Python program for the above approach.
# Function to find the resultant array.
def solve( n,  k,  arr):
     
    for i in range(n-1):
        # checking if aith value less than K
         
        if (arr[i] < k):
             
            # subtracting ai value from K
            k = k - arr[i]
             
            # Adding ai value to an-1
            arr[n - 1] = arr[n - 1] + arr[i]
             
            arr[i] = 0
             
        # if arr[i] value is greater than  K
        else:
            arr[i] = arr[i] - k
            arr[n - 1] = arr[n - 1] + k
            k = 0
             
    # sorting the given array
    # to know about this function
    # check gfg stl sorting article
    arr.sort()
     
    # Displaying the final array
    for i in range(n):
        print(arr[i], end = " ")
 
# Driver code
N = 6
K = 2
arr = [ 3, 1, 4, 6, 2, 5 ]
 
solve(N, K, arr)
 
# This code is contributed by shivanisinghss2110

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Function to find the resultant array.
  static void solve(int n, int k, int []arr)
  {
 
    for (int i = 0; i < n - 1; i++) {
 
      // checking if aith value less than K
      if (arr[i] < k)
 
      {
 
        // subtracting ai value from K
        k = k - arr[i];
 
        // Adding ai value to an-1
        arr[n - 1]
          = arr[n - 1]
          + arr[i];
 
        arr[i] = 0;
      }
 
      // if arr[i] value is greater than  K
      else {
 
        arr[i] = arr[i] - k;
        arr[n - 1] = arr[n - 1] + k;
        k = 0;
      }
    }
 
    // sorting the given array
    // to know about this function
    // check gfg stl sorting article
    Array.Sort(arr);
 
    // Displaying the readonly array
    for (int i = 0; i < n; i++)
      Console.Write( arr[i] + " ");
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int N = 6;
    int K = 2;
    int []arr = { 3, 1, 4, 6, 2, 5 };
 
    solve(N, K, arr);
  }
}
 
// This code is contributed by shikhasingrajput

<script>
// javascript program for the above approach
 
  // Function to find the resultant array.
function solve(n , k , arr)
{
 
    for (var i = 0; i < n - 1; i++) {
 
        // checking if aith value less than K
        if (arr[i] < k)
 
        {
           
            // subtracting ai value from K
            k = k - arr[i];
 
            // Adding ai value to an-1
            arr[n - 1]
                = arr[n - 1]
                  + arr[i];
 
            arr[i] = 0;
        }
 
        // if arr[i] value is greater than  K
        else {
 
            arr[i] = arr[i] - k;
            arr[n - 1] = arr[n - 1] + k;
            k = 0;
        }
    }
 
    // sorting the given array
    // to know about this function
    // check gfg stl sorting article
    arr.sort();
 
    // Displaying the final array
    for (var i = 0; i < n; i++)
        document.write( arr[i] + " ");
}
 
// Driver code
    var N = 6;
    var K = 2;
    var arr = [ 3, 1, 4, 6, 2, 5 ];
 
    solve(N, K, arr);
 
// This code contributed by shikhasingrajput
</script>

1 1 2 4 6 7 

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)