Dada una array arr[] de tamaño N , la tarea es encontrar el elemento de array indexado más pequeño cuyo signo debe invertirse de modo que la suma de la array dada se convierta en 0 . Si no es posible hacer que la suma de la array sea igual a 0 , imprima -1 .
Ejemplos:
Entrada: arr[] = {1, 3, -5, 3, 4}
Salida: 1
Explicación:
Cambiar el signo de arr[1] modifica arr[] a {1, -3, -5, 3, 4}
Dado que la suma de la array se modifica a 0, la salida requerida es 1.Entrada: arr[] = {1, 2, 4}
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento de la array, voltear el signo del elemento de la array y verificar si la suma de la array cambia a 0 o no. Si se encuentra que es cierto, imprima el índice del elemento actual.
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 find the smallest indexed
// array element required to be flipped to
// make sum of the given array equal to 0
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
int 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 approach
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;
// 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 0 def 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 Code if __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 approach
using 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 0
function 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>
Producción:
1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
Deje que la suma de la array dada sea ArrSum
Suma de la array después de cambiar el signo de cualquier elemento de array UpdatedSum = ArrSum – 2 * arr[i]
Si UpdatedSum = 0 , entonces arr[i] debe ser ArrSum / 2 .
Siga los pasos a continuación para resolver el problema:
- Inicializa una variable, digamos ArrSum , para almacenar la suma de la array dada .
- Recorra la array y para cada elemento de la array, verifique si el valor de (2 * arr[i] == ArrSum) es verdadero o no. Si se encuentra que es cierto, imprima el índice del elemento actual.
- De lo contrario, imprima -1 .
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 find the smallest indexed
// array element required to be flipped to
// make sum of the given array equal to 0
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 Code
int 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 approach
import 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 0 def 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 Code arr = [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 approach
using 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>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA