Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar el número de veces que la diferencia absoluta entre la suma de elementos en índices pares e impares es K después de eliminar cualquier elemento a la vez del dado formación.
Ejemplos:
Entrada: arr[] = {2, 4, 2}, K = 2
Salida: 2
Explicación:
- Eliminar arr[0] modifica arr[] a {4, 2}. Por lo tanto, la diferencia entre la suma de elementos indexados impares y pares es 2.
- Eliminar arr[1] modifica arr[] a {2, 2}. Por lo tanto, la diferencia entre la suma de elementos indexados impares y pares es 0.
- Eliminar arr[2] modifica arr[] a {2, 4}. Por lo tanto, la diferencia entre la suma de elementos indexados impares y pares es 2.
Por lo tanto, el número de veces que la diferencia de la suma del elemento en el índice par e impar es 2 es 2.
Entrada: arr[] = { 1, 1, 1, 1, 1 }, K = 0
Salida: 5
Enfoque ingenuo: el enfoque más simple es eliminar cada elemento de la array uno por uno y, después de cada eliminación, verificar si la diferencia absoluta entre la suma de los elementos en los índices pares e impares es K o no. Si se encuentra que es cierto, entonces incremente el conteo. Después de completar el recorrido de la array, imprima el valor de count .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar arrays Prefix Sum y Suffix Sum . Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays prefixSum[] y suffixSum[] de tamaño (N + 2) como 0 para almacenar la suma de prefijos y sufijos de elementos en índices pares e impares respectivamente.
- Almacene la suma de prefijos de elementos de la array arr[] en índices pares e impares en la array prefixSum[] a partir del índice 2 .
- Almacene la suma de sufijos de los elementos de la array arr[] en índices pares e impares en la array suffixSum[] a partir del índice (N + 1) .
- Inicialice la variable count como 0 para almacenar el número de veces que la diferencia absoluta entre la suma de elementos en índices pares e impares es K
- Recorra la array dada arr[] e incremente el conteo según las siguientes condiciones:
- Si se elimina el elemento actual arr[i] , compruebe si la diferencia absoluta de ( prefixSum[i – 1] + suffix[i + 2] ) y
(prefix[i – 2] + suffix[i + 1]) es K O no. - Si se encuentra que la diferencia es K , incremente el conteo en 1 , de lo contrario verifique el siguiente elemento.
- Si se elimina el elemento actual arr[i] , compruebe si la diferencia absoluta de ( prefixSum[i – 1] + suffix[i + 2] ) y
- Compruebe si la condición es verdadera después de eliminar el elemento 0 y 1 por separado e incremente el recuento en consecuencia.
- Después de los pasos anteriores, se elimina el conteo que da el conteo total de elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the first element is K or not
int findCount0th(vector<int>& arr,
int N, int K)
{
// Stores the sum of elements
// at odd and even indices
int oddsum = 0, evensum = 0;
for (int i = 1; i < N; i += 2) {
oddsum += arr[i];
}
for (int i = 2; i < N; i += 2) {
evensum += arr[i];
}
// Return 1 if difference is K
if (abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the second element is K or not
int findCount1st(vector<int>& arr,
int N, int K)
{
// Stores the sum of elements
// at odd and even indices
int evensum = arr[0], oddsum = 0;
for (int i = 3; i < N; i += 2) {
evensum += arr[i];
}
for (int i = 2; i < N; i += 2) {
oddsum += arr[i];
}
// Return 1 if difference is K
if (abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to count number of elements
// to be removed to make sum of
// differences between odd and even
// indexed elements equal to K
int countTimes(vector<int>& arr, int K)
{
// Size of given array
int N = (int)arr.size();
// Base Conditions
if (N == 1)
return 1;
if (N < 3)
return 0;
if (N == 3) {
int cnt = 0;
cnt += (abs(arr[0] - arr[1])
== K
? 1
: 0)
+ (abs(arr[2] - arr[1])
== K
? 1
: 0)
+ (abs(arr[0] - arr[2])
== K
? 1
: 0);
return cnt;
}
// Stores prefix and suffix sums
vector<int> prefix(N + 2, 0);
vector<int> suffix(N + 2, 0);
// Base assignments
prefix[0] = arr[0];
prefix[1] = arr[1];
suffix[N - 1] = arr[N - 1];
suffix[N - 2] = arr[N - 2];
// Store prefix sums of even
// indexed elements
for (int i = 2; i < N; i += 2) {
prefix[i] = arr[i] + prefix[i - 2];
}
// Store prefix sums of odd
// indexed elements
for (int i = 3; i < N; i += 2) {
prefix[i] = arr[i] + prefix[i - 2];
}
// Similarly, store suffix sums of
// elements at even and odd indices
for (int i = N - 3; i >= 0; i -= 2) {
suffix[i] = arr[i] + suffix[i + 2];
}
for (int i = N - 4; i >= 0; i -= 2) {
suffix[i] = arr[i] + suffix[i + 2];
}
// Stores the count of possible removals
int count = 0;
// Traverse and remove the ith element
for (int i = 2; i < N; i++) {
// If the current element is
// excluded, then previous index
// (i - 1) points to (i + 2)
// and (i - 2) points to (i + 1)
if (abs(prefix[i - 1] + suffix[i + 2]
- prefix[i - 2] - suffix[i + 1])
== K) {
count++;
}
}
// Find count when 0th element is removed
count += findCount0th(arr, N, K);
// Find count when 1st element is removed
count += findCount1st(arr, N, K);
// Count gives the required answer
return count;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 4, 5, 6 };
int K = 2;
// Function call
cout << countTimes(arr, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the first element is K or not
static int findCount0th(int[] arr,
int N, int K)
{
// Stores the sum of elements
// at odd and even indices
int oddsum = 0, evensum = 0;
for (int i = 1; i < N; i += 2) {
oddsum += arr[i];
}
for (int i = 2; i < N; i += 2) {
evensum += arr[i];
}
// Return 1 if difference is K
if (Math.abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the second element is K or not
static int findCount1st(int[] arr,
int N, int K)
{
// Stores the sum of elements
// at odd and even indices
int evensum = arr[0], oddsum = 0;
for (int i = 3; i < N; i += 2) {
evensum += arr[i];
}
for (int i = 2; i < N; i += 2) {
oddsum += arr[i];
}
// Return 1 if difference is K
if (Math.abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to count number of elements
// to be removed to make sum of
// differences between odd and even
// indexed elements equal to K
static int countTimes(int[] arr, int K)
{
// Size of given array
int N = (int)arr.length;
// Base Conditions
if (N == 1)
return 1;
if (N < 3)
return 0;
if (N == 3) {
int cnt = 0;
cnt += (Math.abs(arr[0] - arr[1])
== K
? 1
: 0)
+ (Math.abs(arr[2] - arr[1])
== K
? 1
: 0)
+ (Math.abs(arr[0] - arr[2])
== K
? 1
: 0);
return cnt;
}
// Stores prefix and suffix sums
int[] prefix = new int[N + 2];
int[] suffix = new int[N + 2];
Arrays.fill(prefix, 0);
Arrays.fill(suffix, 0);
// Base assignments
prefix[0] = arr[0];
prefix[1] = arr[1];
suffix[N - 1] = arr[N - 1];
suffix[N - 2] = arr[N - 2];
// Store prefix sums of even
// indexed elements
for (int i = 2; i < N; i += 2) {
prefix[i] = arr[i] + prefix[i - 2];
}
// Store prefix sums of odd
// indexed elements
for (int i = 3; i < N; i += 2) {
prefix[i] = arr[i] + prefix[i - 2];
}
// Similarly, store suffix sums of
// elements at even and odd indices
for (int i = N - 3; i >= 0; i -= 2) {
suffix[i] = arr[i] + suffix[i + 2];
}
for (int i = N - 4; i >= 0; i -= 2) {
suffix[i] = arr[i] + suffix[i + 2];
}
// Stores the count of possible removals
int count = 0;
// Traverse and remove the ith element
for (int i = 2; i < N; i++) {
// If the current element is
// excluded, then previous index
// (i - 1) points to (i + 2)
// and (i - 2) points to (i + 1)
if (Math.abs(prefix[i - 1] + suffix[i + 2]
- prefix[i - 2] - suffix[i + 1])
== K) {
count++;
}
}
// Find count when 0th element is removed
count += findCount0th(arr, N, K);
// Find count when 1st element is removed
count += findCount1st(arr, N, K);
// Count gives the required answer
return count;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 4, 5, 6 };
int K = 2;
// Function call
System.out.println(countTimes(arr, K));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach # Function to check if difference # between the sum of odd and even # indexed elements after removing # the first element is K or not def findCount0th(arr, N, K): # Stores the sum of elements # at odd and even indices oddsum = 0 evensum = 0 for i in range(1, N, 2): oddsum += arr[i] for i in range(2, N, 2): evensum += arr[i] # Return 1 if difference is K if (abs(oddsum - evensum) == K): return 1 else: return 0 # Function to check if difference # between the sum of odd and even # indexed elements after removing # the second element is K or not def findCount1st(arr, N, K): # Stores the sum of elements # at odd and even indices evensum = arr[0] oddsum = 0 for i in range(3, N, 2): evensum += arr[i] for i in range(2, N, 2): oddsum += arr[i] # Return 1 if difference is K if (abs(oddsum - evensum) == K): return 1 else: return 0 # Function to count number of elements # to be removed to make sum of # differences between odd and even # indexed elements equal to K def countTimes(arr, K): # Size of given array N = len(arr) # Base Conditions if (N == 1): return 1 if (N < 3): return 0 if (N == 3): cnt = 0 if abs(arr[0] - arr[1]) == K: cnt += 1 if abs(arr[2] - arr[1]) == K: cnt += 1 if abs(arr[0] - arr[2]) == K: cnt += 1 return cnt # Stores prefix and suffix sums prefix = [0] * (N + 2) suffix = [0] * (N + 2) # Base assignments prefix[0] = arr[0] prefix[1] = arr[1] suffix[N - 1] = arr[N - 1] suffix[N - 2] = arr[N - 2] # Store prefix sums of even # indexed elements for i in range(2, N, 2): prefix[i] = arr[i] + prefix[i - 2] # Store prefix sums of odd # indexed elements for i in range(3, N, 2): prefix[i] = arr[i] + prefix[i - 2] # Similarly, store suffix sums of # elements at even and odd indices for i in range(N - 3, -1, -2): suffix[i] = arr[i] + suffix[i + 2] for i in range( N - 4, -1, -2): suffix[i] = arr[i] + suffix[i + 2] # Stores the count of possible removals count = 0 # Traverse and remove the ith element for i in range(2, N): # If the current element is # excluded, then previous index # (i - 1) points to (i + 2) # and (i - 2) points to (i + 1) if (abs(prefix[i - 1] + suffix[i + 2] - prefix[i - 2] - suffix[i + 1]) == K): count += 1 # Find count when 0th element is removed count += findCount0th(arr, N, K) # Find count when 1st element is removed count += findCount1st(arr, N, K) # Count gives the required answer return count # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 4, 5, 6 ] K = 2 # Function call print(countTimes(arr, K)) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the first element is K or not
static int findCount0th(int[] arr,
int N, int K)
{
// Stores the sum of elements
// at odd and even indices
int oddsum = 0, evensum = 0;
for(int i = 1; i < N; i += 2)
{
oddsum += arr[i];
}
for(int i = 2; i < N; i += 2)
{
evensum += arr[i];
}
// Return 1 if difference is K
if (Math.Abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the second element is K or not
static int findCount1st(int[] arr,
int N, int K)
{
// Stores the sum of elements
// at odd and even indices
int evensum = arr[0], oddsum = 0;
for(int i = 3; i < N; i += 2)
{
evensum += arr[i];
}
for(int i = 2; i < N; i += 2)
{
oddsum += arr[i];
}
// Return 1 if difference is K
if (Math.Abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to count number of elements
// to be removed to make sum of
// differences between odd and even
// indexed elements equal to K
static int countTimes(int[] arr, int K)
{
// Size of given array
int N = (int)arr.Length;
// Base Conditions
if (N == 1)
return 1;
if (N < 3)
return 0;
if (N == 3)
{
int cnt = 0;
cnt += (Math.Abs(arr[0] - arr[1]) == K ? 1 : 0) +
(Math.Abs(arr[2] - arr[1]) == K ? 1 : 0) +
(Math.Abs(arr[0] - arr[2]) == K ? 1 : 0);
return cnt;
}
// Stores prefix and suffix sums
int[] prefix = new int[N + 2];
int[] suffix = new int[N + 2];
for(int i = 0; i < N + 2; i++)
{
prefix[i] = 0;
}
for(int i = 0; i < N + 2; i++)
{
suffix[i] = 0;
}
// Base assignments
prefix[0] = arr[0];
prefix[1] = arr[1];
suffix[N - 1] = arr[N - 1];
suffix[N - 2] = arr[N - 2];
// Store prefix sums of even
// indexed elements
for(int i = 2; i < N; i += 2)
{
prefix[i] = arr[i] + prefix[i - 2];
}
// Store prefix sums of odd
// indexed elements
for(int i = 3; i < N; i += 2)
{
prefix[i] = arr[i] + prefix[i - 2];
}
// Similarly, store suffix sums of
// elements at even and odd indices
for(int i = N - 3; i >= 0; i -= 2)
{
suffix[i] = arr[i] + suffix[i + 2];
}
for(int i = N - 4; i >= 0; i -= 2)
{
suffix[i] = arr[i] + suffix[i + 2];
}
// Stores the count of possible removals
int count = 0;
// Traverse and remove the ith element
for(int i = 2; i < N; i++)
{
// If the current element is
// excluded, then previous index
// (i - 1) points to (i + 2)
// and (i - 2) points to (i + 1)
if (Math.Abs(prefix[i - 1] + suffix[i + 2] -
prefix[i - 2] - suffix[i + 1]) == K)
{
count++;
}
}
// Find count when 0th element is removed
count += findCount0th(arr, N, K);
// Find count when 1st element is removed
count += findCount1st(arr, N, K);
// Count gives the required answer
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 4, 5, 6 };
int K = 2;
// Function call
Console.WriteLine(countTimes(arr, K));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program for the above approach
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the first element is K or not
function findCount0th(arr, N, K)
{
// Stores the sum of elements
// at odd and even indices
let oddsum = 0, evensum = 0;
for(let i = 1; i < N; i += 2)
{
oddsum += arr[i];
}
for(let i = 2; i < N; i += 2)
{
evensum += arr[i];
}
// Return 1 if difference is K
if (Math.abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to check if difference
// between the sum of odd and even
// indexed elements after removing
// the second element is K or not
function findCount1st(arr, N, K)
{
// Stores the sum of elements
// at odd and even indices
let evensum = arr[0], oddsum = 0;
for(let i = 3; i < N; i += 2)
{
evensum += arr[i];
}
for(let i = 2; i < N; i += 2)
{
oddsum += arr[i];
}
// Return 1 if difference is K
if (Math.abs(oddsum - evensum) == K)
return 1;
else
return 0;
}
// Function to count number of elements
// to be removed to make sum of
// differences between odd and even
// indexed elements equal to K
function countTimes(arr, K)
{
// Size of given array
let N = arr.length;
// Base Conditions
if (N == 1)
return 1;
if (N < 3)
return 0;
if (N == 3)
{
let cnt = 0;
cnt += (Math.abs(arr[0] - arr[1]) == K ? 1 : 0) +
(Math.abs(arr[2] - arr[1]) == K ? 1 : 0) +
(Math.abs(arr[0] - arr[2]) == K ? 1 : 0);
return cnt;
}
// Stores prefix and suffix sums
let prefix = new Array(N + 2);
let suffix = new Array(N + 2);
for(let i = 0; i < N + 2; i++)
{
prefix[i] = 0;
}
for(let i = 0; i < N + 2; i++)
{
suffix[i] = 0;
}
// Base assignments
prefix[0] = arr[0];
prefix[1] = arr[1];
suffix[N - 1] = arr[N - 1];
suffix[N - 2] = arr[N - 2];
// Store prefix sums of even
// indexed elements
for(let i = 2; i < N; i += 2)
{
prefix[i] = arr[i] + prefix[i - 2];
}
// Store prefix sums of odd
// indexed elements
for(let i = 3; i < N; i += 2)
{
prefix[i] = arr[i] + prefix[i - 2];
}
// Similarly, store suffix sums of
// elements at even and odd indices
for(let i = N - 3; i >= 0; i -= 2)
{
suffix[i] = arr[i] + suffix[i + 2];
}
for(let i = N - 4; i >= 0; i -= 2)
{
suffix[i] = arr[i] + suffix[i + 2];
}
// Stores the count of possible removals
let count = 0;
// Traverse and remove the ith element
for(let i = 2; i < N; i++)
{
// If the current element is
// excluded, then previous index
// (i - 1) points to (i + 2)
// and (i - 2) points to (i + 1)
if (Math.abs(prefix[i - 1] + suffix[i + 2] -
prefix[i - 2] - suffix[i + 1]) == K)
{
count++;
}
}
// Find count when 0th element is removed
count += findCount0th(arr, N, K);
// Find count when 1st element is removed
count += findCount1st(arr, N, K);
// Count gives the required answer
return count;
}
let arr = [ 1, 2, 4, 5, 6 ];
let K = 2;
// Function call
document.write(countTimes(arr, K));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA