Dada una array arr[] que consta de N enteros cuyos valores absolutos son distintos y un entero K , la tarea es encontrar tal disposición de la array dada mediante las siguientes operaciones, de modo que tenga un prefijo positivo suma exactamente en K lugares:
- Elija dos enteros i , j e intercambie los valores del elemento en los índices i y j , donde 0 ≤ i, j < N e i ≠ j .
- Elija un índice i y cambie su signo, es decir, cambie de positivo a negativo y viceversa donde 0 ≤ i < N .
Ejemplos:
Entrada: arr [] = {1, -2, 4, 5, -3}, K = 3
Salida: {-1, 2, -4, 3, 5}
Explicación:
Las sumas de prefijos de la array dada son {-1 , 1, -3, 0, 5}.
Por lo tanto, exactamente 3 índices tienen suma de prefijo positivo.Entrada: arr[] = {1, 4, 3, 2}, K = 2
Salida: {1, -4, 2, 3}
Explicación:
Las sumas de prefijos de la array dada son 1, -3, -1, 2} .
Por lo tanto, exactamente 2 índices tienen suma de prefijo positivo.
Enfoque: el problema dado se puede resolver observando que se puede obtener la array ordenada usando solo el primer tipo de operación. Y uno puede cambiar cada elemento en elementos positivos usando el segundo tipo de operación. Siga los pasos a continuación para resolver el problema:
- Haga que todos los valores de la array sean positivos usando la segunda operación, es decir, cambie el signo de todos los números negativos a positivo.
- Ordene la array arr[] en orden ascendente y establezca K igual a (N – K) .
- Si la suma de K y la cuenta de 0 en el arreglo dado arr[] es mayor que N , entonces no puede haber ningún arreglo posible. Por lo tanto, imprima «-1» . De lo contrario, realice las siguientes operaciones.
- Recorra la array sobre el rango [0, N – 1] y siga los pasos a continuación:
- Cambie el i- ésimo elemento a negativo mediante la 2ª operación .
- Incremente i en 2 y disminuya K en 1 .
- Si K es igual a 0, entonces rompa.
- Compruebe si K sigue siendo mayor que 0 , luego recorra la array desde el último hasta que K sea mayor que 0 , y cambie cada elemento positivo a negativo y disminuya K en 1 .
- Después de los pasos anteriores, imprima la array como el arreglo requerido.
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 rearrange the array
// according to the given condition
void rearrange(int* a, int n, int x)
{
// Using 2nd operation making
// all values positive
for (int i = 0; i < n; i++)
a[i] = abs(a[i]);
// Sort the array
sort(a, a + n);
// Assign K = N - K
x = n - x;
// Count number of zeros
int z = count(a, a + n, 0);
// If number of zeros if greater
if (x > n - z) {
cout << "-1\n";
return;
}
for (int i = 0; i < n && x > 0;
i += 2) {
// Using 2nd operation convert
// it into one negative
a[i] = -a[i];
x--;
}
for (int i = n - 1; i >= 0
&& x > 0;
i--) {
// Using 2nd operation convert
// it into one negative
if (a[i] > 0) {
a[i] = -a[i];
x--;
}
}
// Print the array
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 0, -2, 4, 5, -3 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
rearrange(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int count(int[] a)
{
int counter = 0;
for(int i = 0; i < a.length; i++)
{
if (a[i] == 0)
{
counter++;
}
}
return counter;
}
// Function to rearrange the array
// according to the given condition
static void rearrange(int[] a, int n, int x)
{
// Using 2nd operation making
// all values positive
for(int i = 0; i < n; i++)
a[i] = Math.abs(a[i]);
// Sort the array
Arrays.sort(a);
// Assign K = N - K
x = n - x;
// Count number of zeros
int z = count(a);
// If number of zeros if greater
if (x > n - z)
{
System.out.println("-1");
return;
}
for(int i = 0; i < n && x > 0; i += 2)
{
// Using 2nd operation convert
// it into one negative
a[i] = -a[i];
x--;
}
for(int i = n - 1; i >= 0 && x > 0; i--)
{
// Using 2nd operation convert
// it into one negative
if (a[i] > 0)
{
a[i] = -a[i];
x--;
}
}
// Print the array
for(int i = 0; i < n; i++)
{
System.out.print(a[i] + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 0, -2, 4, 5, -3 };
int K = 3;
int N = arr.length;
// Function Call
rearrange(arr, N, K);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach
# Function to rearrange the array
# according to the given condition
def rearrange(a, n, x):
# Using 2nd operation making
# all values positive
for i in range(n):
a[i] = abs(a[i])
# Sort the array
a = sorted(a)
# Assign K = N - K
x = n - x;
# Count number of zeros
z = a.count(0)
# If number of zeros if greater
if (x > n - z):
print("-1")
return
for i in range(0, n, 2):
if x <= 0:
break
# Using 2nd operation convert
# it into one negative
a[i] = -a[i]
x -= 1
for i in range(n - 1, -1, -1):
if x <= 0:
break
# Using 2nd operation convert
# it into one negative
if (a[i] > 0):
a[i] = -a[i]
x -= 1
# Print array
for i in range(n):
print(a[i], end = " ")
# Driver Code
if __name__ == '__main__':
arr = [0, -2, 4, 5, -3]
K = 3
N = len(arr)
# Function Call
rearrange(arr, N, K)
# This code is co tributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
static int count(int[] a)
{
int counter = 0;
for(int i = 0; i < a.Length; i++)
{
if (a[i] == 0)
{
counter++;
}
}
return counter;
}
// Function to rearrange the array
// according to the given condition
static void rearrange(int[] a, int n, int x)
{
// Using 2nd operation making
// all values positive
for(int i = 0; i < n; i++)
a[i] = Math.Abs(a[i]);
// Sort the array
Array.Sort(a);
// Assign K = N - K
x = n - x;
// Count number of zeros
int z = count(a);
// If number of zeros if greater
if (x > n - z)
{
Console.WriteLine("-1");
return;
}
for(int i = 0; i < n && x > 0; i += 2)
{
// Using 2nd operation convert
// it into one negative
a[i] = -a[i];
x--;
}
for(int i = n - 1; i >= 0 && x > 0; i--)
{
// Using 2nd operation convert
// it into one negative
if (a[i] > 0)
{
a[i] = -a[i];
x--;
}
}
// Print the array
for(int i = 0; i < n; i++)
{
Console.Write(a[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 0, -2, 4, 5, -3 };
int K = 3;
int N = arr.Length;
// Function Call
rearrange(arr, N, K);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
function count(a)
{
let counter = 0;
for(let i = 0; i < a.length; i++)
{
if (a[i] == 0)
{
counter++;
}
}
return counter;
}
// Function to rearrange the array
// according to the given condition
function rearrange(a, n, x)
{
// Using 2nd operation making
// all values positive
for(let i = 0; i < n; i++)
a[i] = Math.abs(a[i]);
// Sort the array
a.sort();
// Assign K = N - K
x = n - x;
// Count number of zeros
let z = count(a);
// If number of zeros if greater
if (x > n - z)
{
document.write("-1");
return;
}
for(let i = 0; i < n && x > 0; i += 2)
{
// Using 2nd operation convert
// it into one negative
a[i] = -a[i];
x--;
}
for(let i = n - 1; i >= 0 && x > 0; i--)
{
// Using 2nd operation convert
// it into one negative
if (a[i] > 0)
{
a[i] = -a[i];
x--;
}
}
// Print the array
for(let i = 0; i < n; i++)
{
document.write(a[i] + " ");
}
}
// driver function
let arr = [ 0, -2, 4, 5, -3 ];
let K = 3;
let N = arr.length;
// Function Call
rearrange(arr, N, K);
// This code is contributed by souravghosh0416.
</script>
Producción:
0 2 -3 4 5
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA