Reorganizar la array para hacer que el producto de la array de suma de prefijos no sea cero

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *