Dada una array arr[] que contiene N enteros y hay Q consultas donde cada consulta consta de un rango [L, R] . La tarea es encontrar si todos los elementos del rango de índice dado tienen frecuencia uniforme o no.
Ejemplos:
Entrada: arr[] = {1, 1, 2, 2, 1}, Q[][] = {{1, 5}, {1, 4}, {3, 4}}
Salida:
No
Sí
Sí
Entrada: arr[] = {100, 100, 200, 100}, Q[][] = {{1, 4}, {1, 2}}
Salida:
No
Sí
Enfoque ingenuo: un enfoque simple será iterar desde el rango de índice [L, R] para cada una de las consultas y contar la frecuencia de cada elemento en ese rango y verificar que cada elemento ocurra un número par de veces o no. La complejidad de tiempo del peor caso de este enfoque será O (Q * N), donde Q es el número de consultas y N es el número de elementos en la array.
Enfoque eficiente: dado que XOR de dos números iguales es 0 , es decir, si todos los elementos de la array aparecen un número par de veces, entonces el XOR de la array completa será 0 . Lo mismo puede decirse de los elementos en el rango dado [L, R]. Ahora, para verificar si el XOR de todos los elementos en el rango dado es 0 o no, se puede crear una array XOR de prefijo donde preXor[i] almacenará el XOR de los elementos arr[0…i] . Y el XOR de los elementos arr[i…j] se puede calcular fácilmente como preXor[j] ^ preXor[i – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform the given queries
void performQueries(vector<int>& A,
vector<pair<int, int> >& q)
{
int n = (int)A.size();
// Making array 1-indexed
A.insert(A.begin(), 0);
// To store the cumulative xor
vector<int> pref_xor(n + 1, 0);
// Taking cumulative Xor
for (int i = 1; i <= n; ++i) {
pref_xor[i]
= pref_xor[i - 1] ^ A[i];
}
// Iterating over the queries
for (auto i : q) {
int L = i.first, R = i.second;
if (L > R)
swap(L, R);
// If both indices are different and xor
// in the range [L, R] is 0
if (L != R and pref_xor[R] == pref_xor[L - 1])
cout << "Yes\n";
else
cout << "No\n";
}
}
// Driver code
int main()
{
vector<int> Arr = { 1, 1, 2, 2, 1 };
vector<pair<int, int> > q = {
{ 1, 5 },
{ 1, 4 },
{ 3, 4 }
};
performQueries(Arr, q);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to perform the given queries
static void performQueries(int []A,
pair[] q)
{
int n = A.length;
// To store the cumulative xor
int []pref_xor = new int[n + 1];
// Taking cumulative Xor
for (int i = 1; i <=n; ++i)
{
pref_xor[i] = pref_xor[i - 1] ^
A[i - 1];
}
// Iterating over the queries
for (pair i : q)
{
int L = i.first, R = i.second;
if (L > R)
{
int temp = L;
L = R;
R = temp;
}
// If both indices are different and xor
// in the range [L, R] is 0
if (L != R && pref_xor[R] == pref_xor[L - 1])
System.out.println("Yes");
else
System.out.println("No");
}
}
// Driver code
static public void main (String []arg)
{
int []Arr = { 1, 1, 2, 2, 1 };
pair[] q = { new pair(1, 5 ),
new pair(1, 4 ),
new pair(3, 4 ) };
performQueries(Arr, q);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
# Function to perform the given queries
def performQueries(A, q):
n = len(A)
# To store the cumulative xor
pref_xor = [0 for i in range(n + 1)]
# Taking cumulative Xor
for i in range(1, n + 1):
pref_xor[i] = pref_xor[i - 1] ^ A[i - 1]
# Iterating over the queries
for i in q:
L = i[0]
R = i[1]
if (L > R):
L, R = R, L
# If both indices are different and
# xor in the range [L, R] is 0
if (L != R and
pref_xor[R] == pref_xor[L - 1]):
print("Yes")
else:
print("No")
# Driver code
Arr = [1, 1, 2, 2, 1]
q = [[ 1, 5 ],
[ 1, 4 ],
[ 3, 4 ]]
performQueries(Arr, q);
# This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to perform the given queries
static void performQueries(int []A,
pair[] q)
{
int n = A.Length;
// To store the cumulative xor
int []pref_xor = new int[n + 1];
// Taking cumulative Xor
for (int i = 1; i <= n; ++i)
{
pref_xor[i] = pref_xor[i - 1] ^
A[i - 1];
}
// Iterating over the queries
foreach (pair k in q)
{
int L = k.first, R = k.second;
if (L > R)
{
int temp = L;
L = R;
R = temp;
}
// If both indices are different and xor
// in the range [L, R] is 0
if (L != R && pref_xor[R] == pref_xor[L - 1])
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// Driver code
static public void Main (String []arg)
{
int []Arr = { 1, 1, 2, 2, 1 };
pair[] q = {new pair(1, 5 ),
new pair(1, 4 ),
new pair(3, 4 )};
performQueries(Arr, q);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to perform the given queries
function performQueries(A, q) {
let n = A.length
// To store the cumulative xor
let pref_xor = new Array(n + 1).fill(0)
// Taking cumulative Xor
for (let i = 1; i < n + 1; i++) {
pref_xor[i] = pref_xor[i - 1] ^ A[i - 1]
}
// Iterating over the queries
for (let i in q) {
let L = i[0]
let R = i[1];
if (L > R) {
let temp = R;
R = L;
L = temp
}
// If both indices are different and
// xor in the range [L, R] is 0
if ((L != R) && (pref_xor[R] == pref_xor[L - 1]))
document.write("No<br>")
else
document.write("Yes<br>")
}
}
// Driver code
let Arr = [1, 1, 2, 2, 1]
let q = [[1, 5],
[1, 4],
[3, 4]]
performQueries(Arr, q);
// This code is contributed by gfgking
</script>
No Yes Yes
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)