Given an array arr[] of size N, the task is to find the smallest indexed array element whose sign needs to be flipped such that the sum of the given array becomes 0. If it is not possible to make the sum of the array equal to 0, then print -1.
Examples:
Input: arr[] = {1, 3, -5, 3, 4}
Output: 1
Explanation:
Flipping the sign of arr[1] modifies arr[] to {1, -3, -5, 3, 4}
Since the sum of array modifies to 0, the required output is 1.Input: arr[] = {1, 2, 4}
Output: -1
Naive Approach: The simplest approach is to solve this problem is to traverse the array and for each array element, flip the sign of the array element and check if the sum of the array changes to 0 or not. If found to be true, then print the index of the current element.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the smallest indexed// array element required to be flipped to// make sum of the given array equal to 0int smallestIndexArrayElementsFlip( int arr[], int N){ // Stores the required index int pos = -1; // Traverse the given array for (int i = 0; i < N; i++) { // Flip the sign of current element arr[i] *= -1; // Stores the sum of array elements int sum = 0; // Find the sum of the array for (int j = 0; j < N; j++) { // Update sum sum += arr[j]; } // If sum is equal to 0 if (sum == 0) { // Update pos pos = i; break; } // Reset the current element // to its original value else { // Reset the value of arr[i] arr[i] *= -1; } } return pos;}// Driver Codeint main(){ int arr[] = { 1, 3, -5, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); cout << smallestIndexArrayElementsFlip( arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG { // Function to find the smallest indexed // array element required to be flipped to // make sum of the given array equal to 0 static int smallestIndexArrayElementsFlip(int arr[], int N) { // Stores the required index int pos = -1; // Traverse the given array for (int i = 0; i < N; i++) { // Flip the sign of current element arr[i] *= -1; // Stores the sum of array elements int sum = 0; // Find the sum of the array for (int j = 0; j < N; j++) { // Update sum sum += arr[j]; } // If sum is equal to 0 if (sum == 0) { // Update pos pos = i; break; } // Reset the current element // to its original value else { // Reset the value of arr[i] arr[i] *= -1; } } return pos; } // Driver Code public static void main (String[] args) { int arr[] = { 1, 3, -5, 3, 4 }; int N = arr.length; System.out.println(smallestIndexArrayElementsFlip(arr, N)); }}// This code is contributed by AnkThon |
Python3
# Python3 program to implement# the above approach# Function to find the smallest indexed# array element required to be flipped to# make sum of the given array equal to 0def smallestIndexArrayElementsFlip(arr, N): # Stores the required index pos = -1 # Traverse the given array for i in range(N): # Flip the sign of current element arr[i] *= -1 # Stores the sum of array elements sum = 0 # Find the sum of the array for j in range(N): # Update sum sum += arr[j] # If sum is equal to 0 if (sum == 0): # Update pos pos = i break # Reset the current element # to its original value else: # Reset the value of arr[i] arr[i] *= -1 return pos# Driver Codeif __name__ == '__main__': arr = [ 1, 3, -5, 3, 4 ] N = len(arr) print(smallestIndexArrayElementsFlip(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG { // Function to find the smallest indexed // array element required to be flipped to // make sum of the given array equal to 0 static int smallestIndexArrayElementsFlip(int []arr, int N) { // Stores the required index int pos = -1; // Traverse the given array for (int i = 0; i < N; i++) { // Flip the sign of current element arr[i] *= -1; // Stores the sum of array elements int sum = 0; // Find the sum of the array for (int j = 0; j < N; j++) { // Update sum sum += arr[j]; } // If sum is equal to 0 if (sum == 0) { // Update pos pos = i; break; } // Reset the current element // to its original value else { // Reset the value of arr[i] arr[i] *= -1; } } return pos; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 3, -5, 3, 4 }; int N = arr.Length; Console.WriteLine(smallestIndexArrayElementsFlip(arr, N)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the smallest indexed// array element required to be flipped to// make sum of the given array equal to 0function smallestIndexArrayElementsFlip(arr, N){ // Stores the required index var pos = -1; var i,j; // Traverse the given array for (i = 0; i < N; i++) { // Flip the sign of current element arr[i] *= -1; // Stores the sum of array elements var sum = 0; // Find the sum of the array for (j = 0; j < N; j++) { // Update sum sum += arr[j]; } // If sum is equal to 0 if (sum == 0) { // Update pos pos = i; break; } // Reset the current element // to its original value else { // Reset the value of arr[i] arr[i] *= -1; } } return pos;}// Driver Code var arr = [1, 3, -5, 3, 4]; var N = arr.length; document.write(smallestIndexArrayElementsFlip(arr, N));</script> |
Output:
1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the following observations:
Let the sum of the given array be ArrSum
Sum of the array after flipping the sign of any array element UpdatedSum = ArrSum – 2 * arr[i]
If UpdatedSum = 0, then arr[i] must be ArrSum / 2.
Follow the steps below to solve the problem:
- Initialize a variable, say ArrSum, to store the sum of the given array.
- Traverse the array and for each array element, check if the value of (2 * arr[i] == ArrSum) is true or not. If found to be true, then print the index of the current element.
- Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the smallest indexed// array element required to be flipped to// make sum of the given array equal to 0int smallestIndexArrayElementsFlip( int arr[], int N){ // Stores the required index int pos = -1; // Stores the sum of the array int ArrSum = 0; // Traverse the given array for (int i = 0; i < N; i++) { // Update ArrSum ArrSum += arr[i]; } // Traverse the given array for (int i = 0; i < N; i++) { // If sum of array elements double // the value of the current element if (2 * arr[i] == ArrSum) { // Update pos pos = i; break; } } return pos;}// Driver Codeint main(){ int arr[] = { 1, 3, -5, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); cout << smallestIndexArrayElementsFlip( arr, N); return 0;} |
Java
// Java program for above approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Function to find the smallest indexed // array element required to be flipped to // make sum of the given array equal to 0 static int smallestIndexArrayElementsFlip( int arr[], int N) { // Stores the required index int pos = -1; // Stores the sum of the array int ArrSum = 0; // Traverse the given array for (int i = 0; i < N; i++) { // Update ArrSum ArrSum += arr[i]; } // Traverse the given array for (int i = 0; i < N; i++) { // If sum of array elements double // the value of the current element if (2 * arr[i] == ArrSum) { // Update pos pos = i; break; } } return pos; } // Driver function public static void main (String[] args) { int arr[] = { 1, 3, -5, 3, 4 }; int N = arr.length; System.out.println(smallestIndexArrayElementsFlip( arr, N)); }}// This code is contributed by offbeat |
Python3
# Python program to implement# the above approach# Function to find the smallest indexed# array element required to be flipped to# make sum of the given array equal to 0def smallestIndexArrayElementsFlip(arr, N): # Stores the required index pos = -1 # Stores the sum of the array ArrSum = 0 # Traverse the given array for i in range(N): # Update ArrSum ArrSum += arr[i] # Traverse the given array for i in range(N): # If sum of array elements double # the value of the current element if (2 * arr[i] == ArrSum): # Update pos pos = i break return pos# Driver Codearr = [1, 3, -5, 3, 4]N = len(arr)print(smallestIndexArrayElementsFlip( arr, N))# This code is contributed by Dharanendra L V |
C#
// C# program for above approachusing System;class GFG { // Function to find the smallest indexed // array element required to be flipped to // make sum of the given array equal to 0 static int smallestIndexArrayElementsFlip(int[] arr, int N) { // Stores the required index int pos = -1; // Stores the sum of the array int ArrSum = 0; // Traverse the given array for (int i = 0; i < N; i++) { // Update ArrSum ArrSum += arr[i]; } // Traverse the given array for (int i = 0; i < N; i++) { // If sum of array elements double // the value of the current element if (2 * arr[i] == ArrSum) { // Update pos pos = i; break; } } return pos; } // Driver function static public void Main() { int[] arr = new int[] { 1, 3, -5, 3, 4 }; int N = arr.Length; Console.WriteLine( smallestIndexArrayElementsFlip(arr, N)); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// javascript program for the above approach // Function to find the smallest indexed // array element required to be flipped to // make sum of the given array equal to 0 function smallestIndexArrayElementsFlip( arr, N) { // Stores the required index let pos = -1; // Stores the sum of the array let ArrSum = 0; // Traverse the given array for (let i = 0; i < N; i++) { // Update ArrSum ArrSum += arr[i]; } // Traverse the given array for (let i = 0; i < N; i++) { // If sum of array elements double // the value of the current element if (2 * arr[i] == ArrSum) { // Update pos pos = i; break; } } return pos; } // Driver Code let arr = [ 1, 3, -5, 3, 4 ]; let N = arr.length; document.write(smallestIndexArrayElementsFlip( arr, N)); </script></script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
