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++
// 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
// 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
Python3
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por sharathmajjigi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA