Dada una array arr[] y un entero K , la tarea es contar subarreglos de tamaño K en los que cada elemento aparece un número par de veces en el subarreglo.
Ejemplos:
Entrada: arr[] = {1, 4, 2, 10, 2, 10, 0, 20}, K = 4
Salida: 1
Explicación: Solo el subarreglo {2, 10, 2, 10} satisface la condición requerida.Entrada: arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20}, K = 3
Salida: 0
Enfoque ingenuo:
la idea es generar todos los subarreglos de tamaño K y verificar cada uno de ellos si todos sus elementos están presentes incluso varias veces o no.
Complejidad de tiempo: O(N*K)
Enfoque eficiente:
La idea es usar Window Sliding y el concepto XOR aquí.
- Si el K dado es impar , devuelva 0 , ya que se garantiza que al menos un número aparecerá un número impar de veces si K es impar.
- Compruebe si K es mayor que la longitud de arr[] y luego devuelva 0.
- Inicialice las siguientes variables:
- count: almacena el recuento de subarreglos de tamaño K con todos los elementos.
- inicio: elimine el elemento más a la izquierda que ya no forma parte del subarreglo de tamaño k.
- currXor: Almacena Xor del subarreglo actual.
- Calcule el Xor del primer subarreglo de tamaño K y verifique si currXor se convierte en 0 , luego incremente el conteo y actualice currXor eliminando Xor con arr[start] e incremente start en 1.
- Traverse arr[] desde K hasta la longitud de arr[]:
- Actualice currXor haciendo Xor con arr[i] .
- Incremente el recuento si currXor se convierte en 0 ; de lo contrario, ignórelo.
- Actualice currXor eliminando Xor con arr[start] .
- Incremento de inicio en 1.
- Cuenta de retorno .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count subarrays
// of size K with all elements
// having even frequencies
#include<bits/stdc++.h>
using namespace std;
// Function to return count of
// required subarrays
int countSubarray(int arr[], int K,
int N)
{
// If K is odd
if (K % 2 != 0)
// Not possible to have
// any such subarrays
return 0;
if (N < K)
return 0;
// Stores the starting index
// of every subarrays
int start = 0;
int i = 0;
// Stores the count of
// required subarrays
int count = 0;
// Stores Xor of the
// current subarray.
int currXor = arr[i++];
// Xor of first subarray
// of size K
while (i < K)
{
currXor ^= arr[i];
i++;
}
// If all elements appear
// even number of times,
// increase the count of
// such subarrays
if (currXor == 0)
count++;
// Remove the starting element
// from the current subarray
currXor ^= arr[start++];
// Traverse the array
// for the remaining
// subarrays
while (i < N)
{
// Update Xor by adding the
// last element of the
// current subarray
currXor ^= arr[i];
// Increment i
i++;
// If currXor becomes 0,
// then increment count
if (currXor == 0)
count++;
// Update currXor by removing
// the starting element of the
// current subarray
currXor ^= arr[start++];
}
// Return count
return count;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 4, 2, 2, 4 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
cout << (countSubarray(arr, K, N));
}
// This code is contributed by chitranayal
Java
// Java program to count subarrays
// of size K with all elements
// having even frequencies
import java.util.*;
class GFG {
// Function to return count of
// required subarrays
static int countSubarray(int[] arr,
int K, int N)
{
// If K is odd
if (K % 2 != 0)
// Not possible to have
// any such subarrays
return 0;
if (N < K)
return 0;
// Stores the starting index
// of every subarrays
int start = 0;
int i = 0;
// Stores the count of
// required subarrays
int count = 0;
// Stores Xor of the
// current subarray.
int currXor = arr[i++];
// Xor of first subarray
// of size K
while (i < K) {
currXor ^= arr[i];
i++;
}
// If all elements appear
// even number of times,
// increase the count of
// such subarrays
if (currXor == 0)
count++;
// Remove the starting element
// from the current subarray
currXor ^= arr[start++];
// Traverse the array
// for the remaining
// subarrays
while (i < N) {
// Update Xor by adding the
// last element of the
// current subarray
currXor ^= arr[i];
// Increment i
i++;
// If currXor becomes 0,
// then increment count
if (currXor == 0)
count++;
// Update currXor by removing
// the starting element of the
// current subarray
currXor ^= arr[start++];
}
// Return count
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 4, 4, 2, 2, 4 };
int K = 4;
int N = arr.length;
System.out.println(
countSubarray(arr, K, N));
}
}
Python3
# Python3 program to count subarrays # of size K with all elements # having even frequencies # Function to return count of # required subarrays def countSubarray(arr, K, N): # If K is odd if (K % 2 != 0): # Not possible to have # any such subarrays return 0 if (N < K): return 0 # Stores the starting index # of every subarrays start = 0 i = 0 # Stores the count of # required subarrays count = 0 # Stores Xor of the # current subarray. currXor = arr[i] i += 1 # Xor of first subarray # of size K while (i < K): currXor ^= arr[i] i += 1 # If all elements appear # even number of times, # increase the count of # such subarrays if (currXor == 0): count += 1 # Remove the starting element # from the current subarray currXor ^= arr[start] start += 1 # Traverse the array # for the remaining # subarrays while (i < N): # Update Xor by adding the # last element of the # current subarray currXor ^= arr[i] # Increment i i += 1 # If currXor becomes 0, # then increment count if (currXor == 0): count += 1 # Update currXor by removing # the starting element of the # current subarray currXor ^= arr[start] start += 1 # Return count return count # Driver Code if __name__ == '__main__': arr = [ 2, 4, 4, 2, 2, 4 ] K = 4 N = len(arr) print(countSubarray(arr, K, N)) # This code is contributed by mohit kumar 29
C#
// C# program to count subarrays
// of size K with all elements
// having even frequencies
using System;
class GFG{
// Function to return count of
// required subarrays
static int countSubarray(int[] arr,
int K, int N)
{
// If K is odd
if (K % 2 != 0)
// Not possible to have
// any such subarrays
return 0;
if (N < K)
return 0;
// Stores the starting index
// of every subarrays
int start = 0;
int i = 0;
// Stores the count of
// required subarrays
int count = 0;
// Stores Xor of the
// current subarray.
int currXor = arr[i++];
// Xor of first subarray
// of size K
while (i < K)
{
currXor ^= arr[i];
i++;
}
// If all elements appear
// even number of times,
// increase the count of
// such subarrays
if (currXor == 0)
count++;
// Remove the starting element
// from the current subarray
currXor ^= arr[start++];
// Traverse the array
// for the remaining
// subarrays
while (i < N)
{
// Update Xor by adding the
// last element of the
// current subarray
currXor ^= arr[i];
// Increment i
i++;
// If currXor becomes 0,
// then increment count
if (currXor == 0)
count++;
// Update currXor by removing
// the starting element of the
// current subarray
currXor ^= arr[start++];
}
// Return count
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 4, 4, 2, 2, 4 };
int K = 4;
int N = arr.Length;
Console.Write(countSubarray(arr, K, N));
}
}
// This code is contributed by Akanksha_Rai
Javascript
<script>
// Javascript program to count subarrays
// of size K with all elements
// having even frequencies
// Function to return count of
// required subarrays
function countSubarray(arr, K, N)
{
// If K is odd
if (K % 2 != 0)
// Not possible to have
// any such subarrays
return 0;
if (N < K)
return 0;
// Stores the starting index
// of every subarrays
var start = 0;
var i = 0;
// Stores the count of
// required subarrays
var count = 0;
// Stores Xor of the
// current subarray.
var currXor = arr[i];
i++;
// Xor of first subarray
// of size K
while (i < K)
{
currXor ^= arr[i];
i++;
}
// If all elements appear
// even number of times,
// increase the count of
// such subarrays
if (currXor == 0)
count++;
// Remove the starting element
// from the current subarray
currXor ^= arr[start];
start++;
// Traverse the array
// for the remaining
// subarrays
while (i < N)
{
// Update Xor by adding the
// last element of the
// current subarray
currXor ^= arr[i];
// Increment i
i++;
// If currXor becomes 0,
// then increment count
if (currXor == 0)
count++;
// Update currXor by removing
// the starting element of the
// current subarray
currXor ^= arr[start];
start++;
}
// Return count
return count;
}
// Driver Code
var arr = [2, 4, 4, 2, 2, 4];
var K = 4;
var N = arr.length;
document.write(countSubarray(arr, K, N));
</script>
Producción:
3
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)