Reducir cada elemento de la array a la mitad conservando la suma cero

Dada una array arr[] de N enteros con suma total de elementos igual a cero. La tarea es reducir cada elemento a su mitad de modo que la suma total permanezca en cero. Para cada elemento impar X en la array, podría reducirse a (X + 1)/2 o (X – 1)/2 .
Ejemplos: 
 

Entrada: arr[] = {-7, 14, -7} 
Salida: -4 7 -3 
-4 + 7 -3 = 0
Entrada: arr[] = {-14, 14} 
Salida: -7 7 
 

Enfoque: todos los elementos pares podrían dividirse por 2, pero para los elementos impares, deben reducirse alternativamente a (X + 1) / 2 y (X – 1) / 2 para conservar la suma original (es decir, 0) en la array final.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to reduce every
// element to it's half such that
// the total sum remain zero
void half(int arr[], int n)
{
    int i;
     
    // Flag to switch between alternating
    // odd numbers in the array
    int flag = 0;
     
    // For every element of the array
    for (i = 0; i < n; i++)
    {
         
        // If its even then reduce it to half
        if (arr[i] % 2 == 0 )
            cout << arr[i] / 2 << " ";
             
        // If its odd
        else
        {
             
            // Reduce the odd elements
            // alternatively
            if (flag == 0)
            {
                cout << arr[i] / 2 - 1 << " ";
                 
                // Switch flag
                flag = 1;
            }
            else
            {
                int q = arr[i] / 2;
                cout<<q <<" ";
                 
                // Switch flag
                flag = 0;
            }
        }
    }
}
 
// Driver code
int main ()
{
    int arr[] = {-7, 14, -7};
    int len = sizeof(arr)/sizeof(arr[0]);
    half(arr, len) ;
    return 0;
}
 
// This code is contributed by Rajput-Ji

// Java implementation of the above approach
class GFG
{
 
// Function to reduce every
// element to it's half such that
// the total sum remain zero
static void half(int arr[], int n)
{
    int i;
     
    // Flag to switch between alternating
    // odd numbers in the array
    int flag = 0;
     
    // For every element of the array
    for (i = 0; i < n; i++)
    {
         
        // If its even then reduce it to half
        if (arr[i] % 2 == 0 )
            System.out.print(arr[i] / 2 + " ");
             
        // If its odd
        else
        {
             
            // Reduce the odd elements
            // alternatively
            if (flag == 0)
            {
                System.out.print(arr[i] / 2 - 1 + " ");
                 
                // Switch flag
                flag = 1;
            }
            else
            {
                int q = arr[i] / 2;
                System.out.print(q + " ");
                 
                // Switch flag
                flag = 0;
            }
        }
    }
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = {-7, 14, -7};
    int len = arr.length;
    half(arr, len) ;
}
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to reduce every
# element to it's half such that
# the total sum remain zero
def half(arr, n) :
     
    # Flag to switch between alternating
    # odd numbers in the array
    flag = 0
     
    # For every element of the array
    for i in range(n):
         
        # If its even then reduce it to half
        if arr[i] % 2 == 0 :
            print(arr[i]//2, end =" ")
             
        # If its odd
        else :
             
            # Reduce the odd elements
            # alternatively
            if flag == 0:
                print(arr[i]//2, end =" ")
                 
                # Switch flag
                flag = 1
            else :
                q = arr[i]//2
                q+= 1
                print(q, end =" ")
                 
                # Switch flag
                flag = 0
 
# Driver code
arr = [-7, 14, -7]
half(arr, len(arr))

// C# implementation of the above approach
using System;
 
class GFG
{
 
// Function to reduce every
// element to it's half such that
// the total sum remain zero
static void half(int []arr, int n)
{
    int i;
     
    // Flag to switch between alternating
    // odd numbers in the array
    int flag = 0;
     
    // For every element of the array
    for (i = 0; i < n; i++)
    {
         
        // If its even then reduce it to half
        if (arr[i] % 2 == 0 )
            Console.Write(arr[i] / 2 + " ");
             
        // If its odd
        else
        {
             
            // Reduce the odd elements
            // alternatively
            if (flag == 0)
            {
                Console.Write(arr[i] / 2 - 1 + " ");
                 
                // Switch flag
                flag = 1;
            }
            else
            {
                int q = arr[i] / 2;
                Console.Write(q + " ");
                 
                // Switch flag
                flag = 0;
            }
        }
    }
}
 
// Driver code
public static void Main ()
{
    int [] arr = {-7, 14, -7};
    int len = arr.Length;
    half(arr, len) ;
}
}
 
// This code is contributed by mohit kumar 29

<script>
// Javascript implementation of the above approach
 
// Function to reduce every
// element to it's half such that
// the total sum remain zero
function half(arr, n)
{
    let i;
     
    // Flag to switch between alternating
    // odd numbers in the array
    let flag = 0;
     
    // For every element of the array
    for (i = 0; i < n; i++)
    {
         
        // If its even then reduce it to half
        if (arr[i] % 2 == 0 )
            document.write(arr[i] / 2 + " ");
             
        // If its odd
        else
        {
             
            // Reduce the odd elements
            // alternatively
            if (flag == 0)
            {
                document.write(Math.ceil(arr[i] / 2) - 1 + " ");
                 
                // Switch flag
                flag = 1;
            }
            else
            {
                let q = Math.ceil(arr[i] / 2);
                document.write(q + " ");
                 
                // Switch flag
                flag = 0;
            }
        }
    }
}
 
// Driver code
    let arr = [-7, 14, -7];
    let len = arr.length;
    half(arr, len) ;
 
// This code is contributed by _saurabh_jaiswal
</script>

-4 7 -3

Complejidad de tiempo: O (n), ya que estamos atravesando una vez en la array.

Complejidad espacial: O (1), ya que no estamos utilizando ningún espacio adicional.