Dada una array, arr[ ] de tamaño N , la tarea es reorganizar la array dada de modo que el producto de todos los elementos de su array de suma de prefijos no sea igual a 0 . Si no es posible reorganizar la array que satisface la condición dada, imprima -1 .
Ejemplos:
Entrada: arr[] = {1, -1, -2, 3}
Salida: 3 1 -1 -2
Explicación:
la suma de prefijos después de reorganizar la array dada a {3, 1, -1, -2} son {3, 4, 3, 1} y producto de todos los elementos de su prefijo sum array = (3 * 4 * 3 * 1) = 36.
Por lo tanto, el array requerido es {3, 1, -1, -2}Entrada: array = {1, 1, -1, -1}
Salida: -1
Enfoque: la idea es ordenar la array dada en orden ascendente o descendente para que cualquier elemento de su prefijo sume no sea igual a 0 . Siga los pasos a continuación para resolver el problema:
- Calcule la suma de los elementos de la array dada , digamos totalSum .
- Si totalSum = 0 , imprima -1 .
- Si totalSum> 0 , imprima la array dada en orden decreciente para que cualquier elemento de su prefijo sume no sea igual a 0.
- Si totalSum < 0 , imprima la array dada en orden ascendente para que cualquier elemento de su prefijo sume no sea igual a 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print array elements
void printArr(int arr[], int N)
{
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Function to rearrange array
// that satisfies the given condition
void rearrangeArr(int arr[], int N)
{
// Stores sum of elements
// of the given array
int totalSum = 0;
// Calculate totalSum
for (int i = 0; i < N; i++) {
totalSum += arr[i];
}
// If the totalSum is equal to 0
if (totalSum == 0) {
// No possible way to
// rearrange array
cout << "-1" << endl;
}
// If totalSum exceeds 0
else if (totalSum > 0) {
// Rearrange the array
// in descending order
sort(arr, arr + N,
greater<int>());
printArr(arr, N);
}
// Otherwise
else {
// Rearrange the array
// in ascending order
sort(arr, arr + N);
printArr(arr, N);
}
}
// Driver Code
int main()
{
int arr[] = { 1, -1, -2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
rearrangeArr(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to print array elements
static void printArr(int arr[], int N)
{
for(int i = 0; i < N; i++)
{
System.out.print(arr[i] + " ");
}
}
// Function to rearrange array
// that satisfies the given condition
static void rearrangeArr(int arr[], int N)
{
// Stores sum of elements
// of the given array
int totalSum = 0;
// Calculate totalSum
for(int i = 0; i < N; i++)
{
totalSum += arr[i];
}
// If the totalSum is equal to 0
if (totalSum == 0)
{
// No possible way to
// rearrange array
System.out.print("-1" + "\n");
}
// If totalSum exceeds 0
else if (totalSum > 0)
{
// Rearrange the array
// in descending order
Arrays.sort(arr);
arr = reverse(arr);
printArr(arr, N);
}
// Otherwise
else
{
// Rearrange the array
// in ascending order
Arrays.sort(arr);
printArr(arr, N);
}
}
static int[] reverse(int a[])
{
int i, n = a.length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, -1, -2, 3 };
int N = arr.length;
rearrangeArr(arr, N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement # the above approach # Function to rearrange array # that satisfies the given condition def rearrangeArr(arr, N): # Stores sum of elements # of the given array totalSum = 0 # Calculate totalSum for i in range(N): totalSum += arr[i] # If the totalSum is equal to 0 if (totalSum == 0): # No possible way to # rearrange array print(-1) # If totalSum exceeds 0 elif (totalSum > 0): # Rearrange the array # in descending order arr.sort(reverse = True) print(*arr, sep = ' ') # Otherwise else: # Rearrange the array # in ascending order arr.sort() print(*arr, sep = ' ') # Driver Code arr = [ 1, -1, -2, 3 ] N = len(arr) rearrangeArr(arr, N); # This code is contributed by avanitrachhadiya2155
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to print array elements
static void printArr(int []arr, int N)
{
for(int i = 0; i < N; i++)
{
Console.Write(arr[i] + " ");
}
}
// Function to rearrange array
// that satisfies the given condition
static void rearrangeArr(int []arr, int N)
{
// Stores sum of elements
// of the given array
int totalSum = 0;
// Calculate totalSum
for(int i = 0; i < N; i++)
{
totalSum += arr[i];
}
// If the totalSum is equal to 0
if (totalSum == 0)
{
// No possible way to
// rearrange array
Console.Write("-1" + "\n");
}
// If totalSum exceeds 0
else if (totalSum > 0)
{
// Rearrange the array
// in descending order
Array.Sort(arr);
arr = reverse(arr);
printArr(arr, N);
}
// Otherwise
else
{
// Rearrange the array
// in ascending order
Array.Sort(arr);
printArr(arr, N);
}
}
static int[] reverse(int []a)
{
int i, n = a.Length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, -1, -2, 3 };
int N = arr.Length;
rearrangeArr(arr, N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript program to implement
// the above approach
// Function to print array elements
function printArr(arr, N)
{
for(var i = 0; i < N; i++)
{
document.write(arr[i] + " ");
}
}
// Function to rearrange array
// that satisfies the given condition
function rearrangeArr(arr, N)
{
// Stores sum of elements
// of the given array
var totalSum = 0;
// Calculate totalSum
for(var i = 0; i < N; i++)
{
totalSum += arr[i];
}
// If the totalSum is equal to 0
if (totalSum == 0)
{
// No possible way to
// rearrange array
document.write("-1" + "<br>");
}
// If totalSum exceeds 0
else if (totalSum > 0)
{
// Rearrange the array
// in descending order
arr.sort(compare);
arr = reverse(arr);
printArr(arr, N);
}
// Otherwise
else
{
// Rearrange the array
// in ascending order
arr.sort(compare);
printArr(arr, N);
}
}
function compare(a, b) {
if (a < b) {
return -1;
} else if (a > b) {
return 1;
} else {
return 0;
}
}
function reverse(a)
{
var i, n = a.length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
var arr = [ 1, -1, -2, 3 ] ;
var N = arr.length;
rearrangeArr(arr, N);
</script>
Producción:
3 1 -1 -2
Complejidad de tiempo: O(N logN)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por ArifShaikh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA