Encuentre el elemento cuya multiplicación con -1 hace que la suma de la array sea 0

Dada una array de N enteros. La tarea es encontrar el índice más pequeño de un elemento tal que cuando se multiplique por -1, la suma de toda la array se convierta en 0. Si no existe tal índice, devuelve -1.
Ejemplos: 
 

Input : arr[] = {1, 3, -5, 3, 4}
Output : 2

Input : arr[] = {5, 3, 6, -7, -4}
Output : -1

Enfoque ingenuo:
la solución simple será tomar cada elemento, multiplicarlo por -1 y verificar si la nueva suma es 0. Este algoritmo funciona en O (N ² ) .
Enfoque eficiente:
si tomamos S como nuestra suma inicial de la array y multiplicamos el elemento actual A _i por -1, entonces la nueva suma se convertirá en S – 2*A _i y esto debería ser igual a 0. Entonces, cuando por primera vez S = 2*A _i entonces el índice actual es nuestro requerido y si ningún elemento satisface la condición entonces nuestra respuesta será -1. La complejidad temporal de este algoritmo es O(N) .
A continuación se muestra la implementación de la idea anterior:
 

// C++ program to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
int minIndex(int arr[], int n)
{
    // Find array sum
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Find element with value equal to sum/2
    for (int i = 0; i < n; i++) {
 
        // when sum is equal to 2*element
        // then this is our required element
        if (2 * arr[i] == sum)
            return (i + 1);
    }
 
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, -5, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minIndex(arr, n) << endl;
    return 0;
}

// Java program to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
 
import java.io.*;
 
class GFG {
    
// Function to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
 static int minIndex(int arr[], int n)
{
    // Find array sum
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Find element with value equal to sum/2
    for (int i = 0; i < n; i++) {
 
        // when sum is equal to 2*element
        // then this is our required element
        if (2 * arr[i] == sum)
            return (i + 1);
    }
 
    return -1;
}
 
// Driver code
 
 
    public static void main (String[] args) {
            int []arr = { 1, 3, -5, 3, 4 };
    int n =arr.length;
    System.out.print( minIndex(arr, n));
    }
}
 
// This code is contributed by anuj_67..

# Python 3 program to find minimum index
# such that sum becomes 0 when the
# element is multiplied by -1
 
# Function to find minimum index
# such that sum becomes 0 when the
# element is multiplied by -1
def minIndex(arr, n):
 
    # Find array sum
    sum = 0
    for i in range (0, n):
        sum += arr[i]
 
    # Find element with value
    # equal to sum/2
    for i in range(0, n):
 
        # when sum is equal to 2*element
        # then this is our required element
        if (2 * arr[i] == sum):
            return (i + 1)
 
    return -1
 
# Driver code
arr = [ 1, 3, -5, 3, 4 ];
n = len(arr);
print(minIndex(arr, n))
 
# This code is contributed
# by Akanksha Rai

// C# program to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
  
using System;
  
class GFG {
     
// Function to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
 static int minIndex(int[] arr, int n)
{
    // Find array sum
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
  
    // Find element with value equal to sum/2
    for (int i = 0; i < n; i++) {
  
        // when sum is equal to 2*element
        // then this is our required element
        if (2 * arr[i] == sum)
            return (i + 1);
    }
  
    return -1;
}
  
// Driver code
  
  
    public static void Main () {
            int[] arr = { 1, 3, -5, 3, 4 };
    int n =arr.Length;
    Console.Write( minIndex(arr, n));
    }
}

<?php
// PHP program to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
 
// Function to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
function minIndex(&$arr, $n)
{
    // Find array sum
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $arr[$i];
 
    // Find element with value equal to sum/2
    for ($i = 0; $i < $n; $i++)
    {
 
        // when sum is equal to 2*element
        // then this is our required element
        if (2 * $arr[$i] == $sum)
            return ($i + 1);
    }
    return -1;
}
 
// Driver code
$arr = array(1, 3, -5, 3, 4 );
$n = sizeof($arr);
echo (minIndex($arr, $n));
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
 
// Javascript program to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1   
 
// Function to find minimum index
// such that sum becomes 0 when the
// element is multiplied by -1
    function minIndex(arr , n)
    {
        // Find array sum
        var sum = 0;
        for (i = 0; i < n; i++)
            sum += arr[i];
 
        // Find element with value equal to sum/2
        for (i = 0; i < n; i++) {
 
            // when sum is equal to 2*element
            // then this is our required element
            if (2 * arr[i] == sum)
                return (i + 1);
        }
 
        return -1;
    }
 
    // Driver code
 
     
        var arr = [ 1, 3, -5, 3, 4 ];
        var n = arr.length;
        document.write(minIndex(arr, n));
 
// This code contributed by Rajput-Ji
 
</script>

2

Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.

Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.