Dada una array , arr[] de tamaño N , la tarea es encontrar el recuento de índices de array de modo que al eliminar un elemento de estos índices, la suma de los elementos de array indexados pares e impares sea igual.
Ejemplos:
Entrada: arr[] = { 2, 1, 6, 4 }
Salida: 1
Explicación:
Eliminar arr[1] de la array modifica arr[] a { 2, 6, 4 } de modo que, arr[0] + arr[ 2] = array[1].
Por lo tanto, la salida requerida es 1.Entrada: arr[] = { 1, 1, 1 }
Salida: 3
Explicación:
Eliminar arr[0] de la array dada modifica arr[] a { 1, 1 } tal que arr[0] = arr[1]
Eliminar arr [1] de la array dada modifica arr[] a { 1, 1 } tal que arr[0] = arr[1]
Eliminar arr[2] de la array dada modifica arr[] a { 1, 1 } tal que arr [0] = arr[1]
Por lo tanto, la salida requerida es 3.
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento de la array, verificar si eliminar el elemento de la array hace que la suma de los elementos de la array indexados pares e impares sea igual o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que la eliminación de cualquier elemento de la array dada hace que los índices pares de los elementos sucesivos sean impares y los índices impares de los elementos sucesivos sean pares. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos evenSum y oddSum , para almacenar la suma de elementos indexados impares e indexados pares de la array dada, respectivamente.
- Recorre la array usando la variable i .
- Elimine cada i -ésimo elemento de la array y actualice la suma de los elementos indexados pares restantes y los elementos indexados impares en función de la observación anterior. Comprueba si las sumas son iguales o no. Si se encuentra que es cierto, entonces incremente el conteo.
- Finalmente, imprima el conteo obtenido.
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 count array indices
// whose removal makes sum of odd and
// even indexed elements equal
int cntIndexesToMakeBalance(int arr[], int n)
{
// If size of the array is 1
if (n == 1) {
return 1;
}
// If size of the array is 2
if (n == 2)
return 0;
// Stores sum of even-indexed
// elements of the given array
int sumEven = 0;
// Stores sum of odd-indexed
// elements of the given array
int sumOdd = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// If i is an even number
if (i % 2 == 0) {
// Update sumEven
sumEven += arr[i];
}
// If i is an odd number
else {
// Update sumOdd
sumOdd += arr[i];
}
}
// Stores sum of even-indexed
// array elements till i-th index
int currOdd = 0;
// Stores sum of odd-indexed
// array elements till i-th index
int currEven = arr[0];
// Stores count of indices whose
// removal makes sum of odd and
// even indexed elements equal
int res = 0;
// Stores sum of even-indexed elements
// after removing the i-th element
int newEvenSum = 0;
// Stores sum of odd-indexed elements
// after removing the i-th element
int newOddSum = 0;
// Traverse the array
for (int i = 1; i < n - 1; i++) {
// If i is an odd number
if (i % 2) {
// Update currOdd
currOdd += arr[i];
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd;
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven - arr[i];
}
// If i is an even number
else {
// Update currEven
currEven += arr[i];
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven;
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd - arr[i];
}
// If newEvenSum is equal to newOddSum
if (newEvenSum == newOddSum) {
// Increase the count
res++;
}
}
// If sum of even-indexed and odd-indexed
// elements is equal by removing the first element
if (sumOdd == sumEven - arr[0]) {
// Increase the count
res++;
}
// If length of the array
// is an odd number
if (n % 2 == 1) {
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumOdd == sumEven - arr[n - 1]) {
// Increase the count
res++;
}
}
// If length of the array
// is an even number
else {
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumEven == sumOdd - arr[n - 1]) {
// Increase the count
res++;
}
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << cntIndexesToMakeBalance(arr, n);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG {
// Function to count array indices
// whose removal makes sum of odd and
// even indexed elements equal
static int cntIndexesToMakeBalance(int arr[], int n)
{
// If size of the array is 1
if (n == 1)
{
return 1;
}
// If size of the array is 2
if (n == 2)
return 0;
// Stores sum of even-indexed
// elements of the given array
int sumEven = 0;
// Stores sum of odd-indexed
// elements of the given array
int sumOdd = 0;
// Traverse the array
for (int i = 0; i < n; i++)
{
// If i is an even number
if (i % 2 == 0)
{
// Update sumEven
sumEven += arr[i];
}
// If i is an odd number
else
{
// Update sumOdd
sumOdd += arr[i];
}
}
// Stores sum of even-indexed
// array elements till i-th index
int currOdd = 0;
// Stores sum of odd-indexed
// array elements till i-th index
int currEven = arr[0];
// Stores count of indices whose
// removal makes sum of odd and
// even indexed elements equal
int res = 0;
// Stores sum of even-indexed elements
// after removing the i-th element
int newEvenSum = 0;
// Stores sum of odd-indexed elements
// after removing the i-th element
int newOddSum = 0;
// Traverse the array
for (int i = 1; i < n - 1; i++)
{
// If i is an odd number
if (i % 2 != 0)
{
// Update currOdd
currOdd += arr[i];
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd;
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven - arr[i];
}
// If i is an even number
else
{
// Update currEven
currEven += arr[i];
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven;
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd - arr[i];
}
// If newEvenSum is equal to newOddSum
if (newEvenSum == newOddSum)
{
// Increase the count
res++;
}
}
// If sum of even-indexed and odd-indexed
// elements is equal by removing the first element
if (sumOdd == sumEven - arr[0])
{
// Increase the count
res++;
}
// If length of the array
// is an odd number
if (n % 2 == 1)
{
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumOdd == sumEven - arr[n - 1])
{
// Increase the count
res++;
}
}
// If length of the array
// is an even number
else
{
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumEven == sumOdd - arr[n - 1])
{
// Increase the count
res++;
}
}
return res;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 1, 1 };
int n = arr.length;
System.out.println(cntIndexesToMakeBalance(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to implement # the above approach # Function to count array indices # whose removal makes sum of odd and # even indexed elements equal def cntIndexesToMakeBalance(arr, n): # If size of the array is 1 if (n == 1): return 1 # If size of the array is 2 if (n == 2): return 0 # Stores sum of even-indexed # elements of the given array sumEven = 0 # Stores sum of odd-indexed # elements of the given array sumOdd = 0 # Traverse the array for i in range(n): # If i is an even number if (i % 2 == 0): # Update sumEven sumEven += arr[i] # If i is an odd number else: # Update sumOdd sumOdd += arr[i] # Stores sum of even-indexed # array elements till i-th index currOdd = 0 # Stores sum of odd-indexed # array elements till i-th index currEven = arr[0] # Stores count of indices whose # removal makes sum of odd and # even indexed elements equal res = 0 # Stores sum of even-indexed elements # after removing the i-th element newEvenSum = 0 # Stores sum of odd-indexed elements # after removing the i-th element newOddSum = 0 # Traverse the array for i in range(1, n - 1): # If i is an odd number if (i % 2): # Update currOdd currOdd += arr[i] # Update newEvenSum newEvenSum = (currEven + sumOdd - currOdd) # Update newOddSum newOddSum = (currOdd + sumEven - currEven - arr[i]) # If i is an even number else: # Update currEven currEven += arr[i] # Update newOddSum newOddSum = (currOdd + sumEven - currEven) # Update newEvenSum newEvenSum = (currEven + sumOdd - currOdd - arr[i]) # If newEvenSum is equal to newOddSum if (newEvenSum == newOddSum): # Increase the count res += 1 # If sum of even-indexed and odd-indexed # elements is equal by removing the first # element if (sumOdd == sumEven - arr[0]): # Increase the count res += 1 # If length of the array # is an odd number if (n % 2 == 1): # If sum of even-indexed and odd-indexed # elements is equal by removing the last # element if (sumOdd == sumEven - arr[n - 1]): # Increase the count res += 1 # If length of the array # is an even number else: # If sum of even-indexed and odd-indexed # elements is equal by removing the last # element if (sumEven == sumOdd - arr[n - 1]): # Increase the count res += 1 return res # Driver Code if __name__ == "__main__" : arr = [ 1, 1, 1 ] n = len(arr) print(cntIndexesToMakeBalance(arr, n)) # This code is contributed by AnkitRai01
C#
// C# program to implement
// the above approach
using System;
class GFG {
// Function to count array indices
// whose removal makes sum of odd and
// even indexed elements equal
static int cntIndexesToMakeBalance(int[] arr, int n)
{
// If size of the array is 1
if (n == 1)
{
return 1;
}
// If size of the array is 2
if (n == 2)
return 0;
// Stores sum of even-indexed
// elements of the given array
int sumEven = 0;
// Stores sum of odd-indexed
// elements of the given array
int sumOdd = 0;
// Traverse the array
for (int i = 0; i < n; i++)
{
// If i is an even number
if (i % 2 == 0)
{
// Update sumEven
sumEven += arr[i];
}
// If i is an odd number
else
{
// Update sumOdd
sumOdd += arr[i];
}
}
// Stores sum of even-indexed
// array elements till i-th index
int currOdd = 0;
// Stores sum of odd-indexed
// array elements till i-th index
int currEven = arr[0];
// Stores count of indices whose
// removal makes sum of odd and
// even indexed elements equal
int res = 0;
// Stores sum of even-indexed elements
// after removing the i-th element
int newEvenSum = 0;
// Stores sum of odd-indexed elements
// after removing the i-th element
int newOddSum = 0;
// Traverse the array
for (int i = 1; i < n - 1; i++)
{
// If i is an odd number
if (i % 2 != 0)
{
// Update currOdd
currOdd += arr[i];
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd;
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven - arr[i];
}
// If i is an even number
else
{
// Update currEven
currEven += arr[i];
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven;
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd - arr[i];
}
// If newEvenSum is equal to newOddSum
if (newEvenSum == newOddSum)
{
// Increase the count
res++;
}
}
// If sum of even-indexed and odd-indexed
// elements is equal by removing the first element
if (sumOdd == sumEven - arr[0])
{
// Increase the count
res++;
}
// If length of the array
// is an odd number
if (n % 2 == 1)
{
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumOdd == sumEven - arr[n - 1])
{
// Increase the count
res++;
}
}
// If length of the array
// is an even number
else
{
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumEven == sumOdd - arr[n - 1])
{
// Increase the count
res++;
}
}
return res;
}
// Drivers Code
public static void Main ()
{
int[] arr = { 1, 1, 1 };
int n = arr.Length;
Console.WriteLine(cntIndexesToMakeBalance(arr, n));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count array indices
// whose removal makes sum of odd and
// even indexed elements equal
function cntIndexesToMakeBalance(arr, n)
{
// If size of the array is 1
if (n == 1) {
return 1;
}
// If size of the array is 2
if (n == 2)
return 0;
// Stores sum of even-indexed
// elements of the given array
let sumEven = 0;
// Stores sum of odd-indexed
// elements of the given array
let sumOdd = 0;
// Traverse the array
for (let i = 0; i < n; i++) {
// If i is an even number
if (i % 2 == 0) {
// Update sumEven
sumEven += arr[i];
}
// If i is an odd number
else {
// Update sumOdd
sumOdd += arr[i];
}
}
// Stores sum of even-indexed
// array elements till i-th index
let currOdd = 0;
// Stores sum of odd-indexed
// array elements till i-th index
let currEven = arr[0];
// Stores count of indices whose
// removal makes sum of odd and
// even indexed elements equal
let res = 0;
// Stores sum of even-indexed elements
// after removing the i-th element
let newEvenSum = 0;
// Stores sum of odd-indexed elements
// after removing the i-th element
let newOddSum = 0;
// Traverse the array
for (let i = 1; i < n - 1; i++) {
// If i is an odd number
if (i % 2) {
// Update currOdd
currOdd += arr[i];
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd;
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven - arr[i];
}
// If i is an even number
else {
// Update currEven
currEven += arr[i];
// Update newOddSum
newOddSum = currOdd + sumEven
- currEven;
// Update newEvenSum
newEvenSum = currEven + sumOdd
- currOdd - arr[i];
}
// If newEvenSum is equal to newOddSum
if (newEvenSum == newOddSum) {
// Increase the count
res++;
}
}
// If sum of even-indexed and odd-indexed
// elements is equal by removing the first element
if (sumOdd == sumEven - arr[0]) {
// Increase the count
res++;
}
// If length of the array
// is an odd number
if (n % 2 == 1) {
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumOdd == sumEven - arr[n - 1]) {
// Increase the count
res++;
}
}
// If length of the array
// is an even number
else {
// If sum of even-indexed and odd-indexed
// elements is equal by removing the last element
if (sumEven == sumOdd - arr[n - 1]) {
// Increase the count
res++;
}
}
return res;
}
// Driver Code
let arr = [ 1, 1, 1 ];
let n = arr.length;
document.write(cntIndexesToMakeBalance(arr, n));
// This code is contributed by Mayank Tyagi
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA