Dada una array arr[] que consta de N enteros, la tarea es reorganizar la array de modo que la suma de todas las subarreglas a partir del primer índice de la array no sea cero . Si no es posible generar dicho arreglo, imprima “-1” .
Ejemplos:
Entrada: arr[] = {-1, 1, -2, 3}
Salida: {-1, -2, 1, 3}
Explicación: Uno de los posibles reordenamientos es {-1, -2, 1, 3}.
Los subarreglos que comienzan con el índice 0 son {-1}, {-1, -2}, {-1, -2, 1} y {-1, -2, 1, 3}. Ninguno de los subarreglos anteriores tiene suma 0.Entrada: arr[] = {0, 0, 0, 0}
Salida: -1
Enfoque: la array deseada se puede obtener de la array dada si está en cualquiera de las dos configuraciones siguientes:
- Si el arreglo dado se ordena en orden ascendente, el primer subarreglo con suma cero se puede manejar reemplazando el último elemento del subarreglo con un elemento mayor que él.
- De manera similar, en arreglos ordenados en orden descendente , reemplazando el primer elemento del subarreglo con suma cero con un elemento más pequeño que él para asegurar que la suma a partir de entonces sea negativa.
Siga los pasos a continuación para resolver el problema:
- Cuando la array se ordena en orden ascendente:
- Ordene la array arr[] en orden ascendente y encuentre la suma de los primeros i elementos de la array (0 ≤ i ≤ N).
- Cuando encuentre una suma cero, reemplace el elemento que anula la suma del prefijo (es decir, el i -ésimo elemento) con el elemento más grande de la array:
- Si el elemento más grande de la array es igual al número entero que causa la anulación, pase a la segunda configuración.
- Si el elemento más grande es mayor que el elemento problemático, este reemplazo asegura una suma positiva en lugar de cero.
- Cuando la array se ordena en orden descendente:
- Ordene la array arr[] en orden descendente y comience a encontrar la suma de los últimos i elementos de la array (0 ≤ i ≤ N).
- Cuando se encuentre una suma cero, reemplace el elemento que anula la suma del prefijo (es decir, el i -ésimo elemento) con el elemento más pequeño de la array:
- Si el elemento más pequeño de la array es igual al número entero que causa la anulación, entonces no es posible reorganizar la array arr[].
- Si el elemento más pequeño es más pequeño que el elemento problemático, este reemplazo asegura una suma negativa en lugar de cero.
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 such
// that sum of all elements of subarrays
// from the 1st index is non-zero
void rearrangeArray(int a[], int N)
{
// Initialize sum of subarrays
int sum = 0;
// Sum of all elements of array
for (int i = 0; i < N; i++) {
sum += a[i];
}
// If sum is 0, the required
// array could never be formed
if (sum == 0) {
cout << "-1";
return;
}
// If sum is non zero, array
// might be formed
sum = 0;
int b = 0;
// Sort array in ascending order
sort(a, a + N);
for (int i = 0; i < N; i++) {
sum += a[i];
// When current subarray sum
// becomes 0 replace it with
// the largest element
if (sum == 0) {
if (a[i] != a[N - 1]) {
sum -= a[i];
// Swap Operation
swap(a[i], a[N - 1]);
sum += a[i];
}
// If largest element is same
// as element to be replaced,
// then rearrangement impossible
else {
b = 1;
break;
}
}
}
// If b = 1, then rearrangement
// is not possible. Hence check
// with reverse configuration
if (b == 1) {
b = 0;
sum = 0;
// Sort array in descending order
sort(a, a + N, greater<int>());
// When current subarray sum
// becomes 0 replace it with
// the smallest element
for (int i = N - 1; i >= 0; i--) {
sum += a[i];
if (sum == 0) {
if (a[i] != a[0]) {
sum -= a[i];
// Swap Operation
swap(a[i], a[0]);
sum += a[i];
}
// If smallest element is same
// as element to be replaced,
// then rearrangement impossible
else {
b = 1;
break;
}
}
}
}
// If neither of the configurations
// worked then print "-1"
if (b == 1) {
cout << "-1";
return;
}
// Otherwise, print the formed
// rearrangement
for (int i = 0; i < N; i++) {
cout << a[i] << " ";
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, -1, 2, 4, 0 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
rearrangeArray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
class GFG{
// Function to rearrange the array such
// that sum of all elements of subarrays
// from the 1st index is non-zero
static void rearrangeArray(int a[], int N)
{
// Initialize sum of subarrays
int sum = 0;
// Sum of all elements of array
for(int i = 0; i < N; i++)
{
sum += a[i];
}
// If sum is 0, the required
// array could never be formed
if (sum == 0)
{
System.out.print("-1");
return;
}
// If sum is non zero, array
// might be formed
sum = 0;
int b = 0;
// Sort array in ascending order
Arrays.sort(a);
for(int i = 0; i < N; i++)
{
sum += a[i];
// When current subarray sum
// becomes 0 replace it with
// the largest element
if (sum == 0)
{
if (a[i] != a[N - 1])
{
sum -= a[i];
// Swap Operation
int temp = a[i];
a[i] = a[N - 1];
a[N - 1] = temp;
sum += a[i];
}
// If largest element is same
// as element to be replaced,
// then rearrangement impossible
else
{
b = 1;
break;
}
}
}
// If b = 1, then rearrangement
// is not possible. Hence check
// with reverse configuration
if (b == 1)
{
b = 0;
sum = 0;
// Sort array in descending order
Arrays.sort(a);
// When current subarray sum
// becomes 0 replace it with
// the smallest element
for(int i = N - 1; i >= 0; i--)
{
sum += a[i];
if (sum == 0)
{
if (a[i] != a[0])
{
sum -= a[i];
// Swap Operation
int temp = a[i];
a[i] = a[0];
a[0] = temp;
sum += a[i];
}
// If smallest element is same
// as element to be replaced,
// then rearrangement impossible
else
{
b = 1;
break;
}
}
}
}
// If neither of the configurations
// worked then print "-1"
if (b == 1)
{
System.out.print("-1" + " ");
return;
}
// Otherwise, print the formed
// rearrangement
for(int i = 0; i < N; i++)
{
System.out.print(a[i] + " ");
}
}
// Driver Code
public static void main(String args[])
{
// Given array
int arr[] = { 1, -1, 2, 4, 0 };
// Size of array
int N = arr.length;
// Function Call
rearrangeArray(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program for the above approach
# Function to rearrange the array such
# that sum of all elements of subarrays
# from the 1st index is non-zero
def rearrangeArray(a, N):
# Initialize sum of subarrays
sum = 0
# Sum of all elements of array
for i in range(N):
sum += a[i]
# If sum is 0, the required
# array could never be formed
if (sum == 0):
print("-1")
return
# If sum is non zero, array
# might be formed
sum = 0
b = 0
# Sort array in ascending order
a = sorted(a)
for i in range(N):
sum += a[i]
# When current subarray sum
# becomes 0 replace it with
# the largest element
if (sum == 0):
if (a[i] != a[N - 1]):
sum -= a[i]
# Swap Operation
a[i], a[N - 1] = a[N - 1], a[i]
sum += a[i]
# If largest element is same
# as element to be replaced,
# then rearrangement impossible
else:
b = 1
break
# If b = 1, then rearrangement
# is not possible. Hence check
# with reverse configuration
if (b == 1):
b = 0
sum = 0
# Sort array in descending order
a = sorted(a)
a = a[::-1]
# When current subarray sum
# becomes 0 replace it with
# the smallest element
for i in range(N - 1, -1, -1):
sum += a[i]
if (sum == 0):
if (a[i] != a[0]):
sum -= a[i]
# Swap Operation
a[i], a[0] = a[0], a[i]
sum += a[i]
# If smallest element is same
# as element to be replaced,
# then rearrangement impossible
else:
b = 1
break
# If neither of the configurations
# worked then print"-1"
if (b == 1):
print("-1")
return
# Otherwise, print the formed
# rearrangement
for i in range(N):
print(a[i], end = " ")
# Driver Code
if __name__ == '__main__':
# Given array
arr = [ 1, -1, 2, 4, 0 ]
# Size of array
N = len(arr)
# Function Call
rearrangeArray(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to rearrange the array such
// that sum of all elements of subarrays
// from the 1st index is non-zero
static void rearrangeArray(int [] a, int N)
{
// Initialize sum of subarrays
int sum = 0;
// Sum of all elements of array
for(int i = 0; i < N; i++)
{
sum += a[i];
}
// If sum is 0, the required
// array could never be formed
if (sum == 0)
{
Console.Write("-1");
return;
}
// If sum is non zero, array
// might be formed
sum = 0;
int b = 0;
// Sort array in ascending order
Array.Sort(a);
for(int i = 0; i < N; i++)
{
sum += a[i];
// When current subarray sum
// becomes 0 replace it with
// the largest element
if (sum == 0)
{
if (a[i] != a[N - 1])
{
sum -= a[i];
// Swap Operation
int temp = a[i];
a[i] = a[N - 1];
a[N - 1] = temp;
sum += a[i];
}
// If largest element is same
// as element to be replaced,
// then rearrangement impossible
else
{
b = 1;
break;
}
}
}
// If b = 1, then rearrangement
// is not possible. Hence check
// with reverse configuration
if (b == 1)
{
b = 0;
sum = 0;
// Sort array in descending order
Array.Sort(a);
// When current subarray sum
// becomes 0 replace it with
// the smallest element
for(int i = N - 1; i >= 0; i--)
{
sum += a[i];
if (sum == 0)
{
if (a[i] != a[0])
{
sum -= a[i];
// Swap Operation
int temp = a[i];
a[i] = a[0];
a[0] = temp;
sum += a[i];
}
// If smallest element is same
// as element to be replaced,
// then rearrangement impossible
else
{
b = 1;
break;
}
}
}
}
// If neither of the configurations
// worked then print "-1"
if (b == 1)
{
Console.Write("-1" + " ");
return;
}
// Otherwise, print the formed
// rearrangement
for(int i = 0; i < N; i++)
{
Console.Write(a[i] + " ");
}
}
// Driver Code
public static void Main()
{
// Given array
int[] arr = { 1, -1, 2, 4, 0 };
// Size of array
int N = arr.Length;
// Function Call
rearrangeArray(arr, N);
}
}
// This code is contributed by chitranayal
Javascript
<script>
// javascript program for the
// above approach
// Function to rearrange the array such
// that sum of all elements of subarrays
// from the 1st index is non-zero
function rearrangeArray(a, N)
{
// Initialize sum of subarrays
let sum = 0;
// Sum of all elements of array
for(let i = 0; i < N; i++)
{
sum += a[i];
}
// If sum is 0, the required
// array could never be formed
if (sum == 0)
{
document.write("-1");
return;
}
// If sum is non zero, array
// might be formed
sum = 0;
let b = 0;
// Sort array in ascending order
a.sort();
for(let i = 0; i < N; i++)
{
sum += a[i];
// When current subarray sum
// becomes 0 replace it with
// the largest element
if (sum == 0)
{
if (a[i] != a[N - 1])
{
sum -= a[i];
// Swap Operation
let temp = a[i];
a[i] = a[N - 1];
a[N - 1] = temp;
sum += a[i];
}
// If largest element is same
// as element to be replaced,
// then rearrangement impossible
else
{
b = 1;
break;
}
}
}
// If b = 1, then rearrangement
// is not possible. Hence check
// with reverse configuration
if (b == 1)
{
b = 0;
sum = 0;
// Sort array in descending order
a.sort();
// When current subarray sum
// becomes 0 replace it with
// the smallest element
for(let i = N - 1; i >= 0; i--)
{
sum += a[i];
if (sum == 0)
{
if (a[i] != a[0])
{
sum -= a[i];
// Swap Operation
let temp = a[i];
a[i] = a[0];
a[0] = temp;
sum += a[i];
}
// If smallest element is same
// as element to be replaced,
// then rearrangement impossible
else
{
b = 1;
break;
}
}
}
}
// If neither of the configurations
// worked then print "-1"
if (b == 1)
{
document.write("-1" + " ");
return;
}
// Otherwise, print the formed
// rearrangement
for(let i = 0; i < N; i++)
{
document.write(a[i] + " ");
}
}
// Driver Code
// Given array
let arr = [ 1, -1, 2, 4, 0 ];
// Size of array
let N = arr.length;
// Function Call
rearrangeArray(arr, N);
</script>
Producción:
-1 0 4 2 1
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA