# Find the element whose multiplication with -1 makes array sum 0

Given an array of N integers. The task is to find the smallest index of an element such that when multiplied by -1 the sum of whole array becomes 0. If there is no such index return -1.**Examples:**

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Naive Approach :**

The simple solution will be to take each element, multiply it by -1 and check if the new sum is 0. This algorithm works in **O(N ^{2})**.

**Efficient Approach :**

If we take S as our initial sum of the array and we multiply current element A

_{i}by -1 then the new sum will become S – 2*A

_{i}and this should be equal to 0. So when for the first time

**S = 2*A**then the current index is our required and if no element satisfies the condition then our answer will be -1. The time complexity of this algorithm is

_{i}**O(N)**.

Below is the implementation of the above idea :

## C++

`// 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

`// 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

`# 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#

`// 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` `// 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` `?>` |

## Javascript

`<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>` |

**Output:**

2