Dada una array arr[] que consiste en N enteros positivos y un entero positivo X , la tarea es encontrar el número de pares (i, j) tales que i < j y (arr[i]^arr[j] )&X es 0 _
Ejemplos:
Entrada: arr[] = {1, 3, 4, 2}, X = 2
Salida: 2
Explicación:
Los siguientes son los pares posibles de la array dada:
- (0, 2): El valor de (arr[0]^arr[2])&X es (1^4)&2 = 0.
- (1, 3): El valor de (arr[1]^arr[3])&X es (3^2)&2 = 0.
Por lo tanto, la cuenta total de pares es 2.
Entrada: arr[] = {3, 2, 5, 4, 6, 7}, X = 6
Salida: 3
Enfoque ingenuo: el enfoque simple para resolver el problema dado es generar todos los pares posibles de la array dada y contar esos pares (i, j) que satisfacen los criterios dados, es decir, i < j y (arr[i]^arr[j ] )&X es 0 .. Después de verificar todos los pares, imprima el conteo total obtenido.
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 find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
int countOfPairs(int arr[], int N, int X)
{
// Stores the resultant count
// of pairs
int count = 0;
// Iterate over the range [0, N)
for (int i = 0; i < N - 1; i++) {
// Iterate over the range
for (int j = i + 1; j < N; j++) {
// Check for the given
// condition
if (((arr[i] ^ arr[j]) & X) == 0)
count++;
}
}
// Return the resultant count
return count;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 5, 4, 6, 7 };
int X = 6;
int N = sizeof(arr) / sizeof(arr[0]);
cout << countOfPairs(arr, N, X);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
public static int countOfPairs(int arr[], int N, int X)
{
// Stores the resultant count
// of pairs
int count = 0;
// Iterate over the range [0, N)
for (int i = 0; i < N - 1; i++) {
// Iterate over the range
for (int j = i + 1; j < N; j++) {
// Check for the given
// condition
if (((arr[i] ^ arr[j]) & X) == 0)
count++;
}
}
// Return the resultant count
return count;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 3, 2, 5, 4, 6, 7 };
int X = 6;
int N = arr.length;
System.out.println(countOfPairs(arr, N, X));
}
}
// This code is contributed by gfgking.
Python3
# Python3 program for the above approach # Function to find the number of pairs # that satisfy the given criteria i.e., # i < j and (arr[i]^arr[j] )&X is 0 def countOfPairs(arr, N, X): # Stores the resultant count # of pairs count = 0 # Iterate over the range [0, N) for i in range(N - 1): # Iterate over the range for j in range(i + 1, N): # Check for the given # condition if (((arr[i] ^ arr[j]) & X) == 0): count += 1 # Return the resultant count return count # Driver Code if __name__ == '__main__': arr = [ 3, 2, 5, 4, 6, 7 ] X = 6 N = len(arr) print(countOfPairs(arr, N, X)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
static int countOfPairs(int []arr, int N, int X)
{
// Stores the resultant count
// of pairs
int count = 0;
// Iterate over the range [0, N)
for(int i = 0; i < N - 1; i++)
{
// Iterate over the range
for(int j = i + 1; j < N; j++)
{
// Check for the given
// condition
if (((arr[i] ^ arr[j]) & X) == 0)
count++;
}
}
// Return the resultant count
return count;
}
// Driver Code
public static void Main()
{
int []arr = { 3, 2, 5, 4, 6, 7 };
int X = 6;
int N = arr.Length;
Console.Write(countOfPairs(arr, N, X));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
function countOfPairs(arr, N, X)
{
// Stores the resultant count
// of pairs
let count = 0;
// Iterate over the range [0, N)
for (let i = 0; i < N - 1; i++)
{
// Iterate over the range
for (let j = i + 1; j < N; j++)
{
// Check for the given
// condition
if (((arr[i] ^ arr[j]) & X) == 0)
count++;
}
}
// Return the resultant count
return count;
}
// Driver Code
let arr = [3, 2, 5, 4, 6, 7];
let X = 6;
let N = arr.length;
document.write(countOfPairs(arr, N, X));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar observando la ecuación dada. Entonces, para realizar (A[i]^A[j]) & X == 0 , luego deshabilite los bits en la respuesta de (A[i]^A[j]) en la misma posición donde la X ha configurado los bits en se requiere su representación binaria .
Por ejemplo, si X = 6 => 110 , entonces para hacer (respuesta & X) == 0 donde respuesta = A[i]^A[j] , la respuesta debería ser 001 o 000 . Entonces, para obtener el bit 0 en la respuesta (en la misma posición que el bit establecido que tiene la X ), se requiere tener el mismo bit en A[i] y A[j] en esa posición como Bitwise XOR del mismo bit (1^1 = 0 y 0^0 = 0) da 0 .
Al observar de cerca la relación entre X y A[i] y A[j] , se encuentra que X&A[i] == X&A[j] . Por lo tanto, la idea es encontrar la frecuencia de los elementos de la array que tienen el valor arr[i]&X y dos números cualesquiera con el mismo valor se pueden formar como un par. Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa desordenado , diga M para almacenar el recuento de números que tienen un valor particular arr[i]^X .
- Iterar sobre el rango [0, N] usando la variable i y aumentar el conteo del valor de arr[i]&X en el mapa desordenado M .
- Inicialice la cuenta variable como 0 para almacenar la cuenta de pares resultante.
- Iterar sobre el mapa M usando la variable m y agregar el valor de (m.segundo)*(m.segundo – 1)/2 a la variable contar .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
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 find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
int countOfPairs(int arr[], int N, int X)
{
// Stores the resultant count
// of pairs
int count = 0;
// Initializing the map M
unordered_map<int, int> M;
// Populating the map
for (int i = 0; i < N; i++) {
M[(arr[i] & X)]++;
}
// Count number of pairs for every
// element in map using mathematical
// concept of combination
for (auto m : M) {
int p = m.second;
// As nC2 = n*(n-1)/2
count += p * (p - 1) / 2;
}
// Return the resultant count
return count;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 5, 4, 6, 7 };
int X = 6;
int N = sizeof(arr) / sizeof(arr[0]);
cout << countOfPairs(arr, N, X);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
static int countOfPairs(int[] arr, int N, int X)
{
// Stores the resultant count
// of pairs
int count = 0;
// Initializing the map M
HashMap<Integer,
Integer> M = new HashMap<Integer,
Integer>();
// Populating the map
for(int i = 0; i < N; i++)
{
if (M.containsKey(arr[i] & X))
M.put((arr[i] & X),
M.get(arr[i] & X) + 1);
else
M.put(arr[i] & X, 1);
}
// Count number of pairs for every
// element in map using mathematical
// concept of combination
for(Integer entry : M.keySet())
{
int p = M.get(entry);
// As nC2 = n*(n-1)/2
count += p * (p - 1) / 2;
}
// Return the resultant count
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 3, 2, 5, 4, 6, 7 };
int X = 6;
int N = arr.length;
System.out.print(countOfPairs(arr, N, X));
}
}
// This code is contributed by ukasp
Python3
# Python3 program for the above approach # Function to find the number of pairs # that satisfy the given criteria i.e., # i < j and (arr[i]^arr[j] )&X is 0 def countOfPairs(arr, N, X): # Stores the resultant count # of pairs count = 0 # Initialize the dictionary M M = dict() # Populate the map for i in range(0, N): k = arr[i] & X if k in M: M[k] += 1 else: M[k] = 1 # Count number of pairs for every # element in map using mathematical # concept of combination for m in M.keys(): p = M[m] # As nC2 = n*(n-1)/2 count += p * (p - 1) // 2 # Return the resultant count return count # Driver Code if __name__ == '__main__': arr = [ 3, 2, 5, 4, 6, 7 ] X = 6 N = len(arr) print(countOfPairs(arr, N, X)) # This code is contributed by MuskanKalra1
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
static int countOfPairs(int []arr, int N, int X)
{
// Stores the resultant count
// of pairs
int count = 0;
// Initializing the map M
Dictionary<int,int> M = new Dictionary<int,int>();
// Populating the map
for (int i = 0; i < N; i++) {
if(M.ContainsKey(arr[i] & X))
M[(arr[i] & X)]++;
else
M.Add(arr[i] & X,1);
}
// Count number of pairs for every
// element in map using mathematical
// concept of combination
foreach(KeyValuePair<int, int> entry in M)
{
int p = entry.Value;
// As nC2 = n*(n-1)/2
count += p * (p - 1) / 2;
}
// Return the resultant count
return count;
}
// Driver Code
public static void Main()
{
int []arr = { 3, 2, 5, 4, 6, 7 };
int X = 6;
int N = arr.Length;
Console.Write(countOfPairs(arr, N, X));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
function countOfPairs(arr, N, X)
{
// Stores the resultant count
// of pairs
let count = 0;
// Initializing the map M
let M = new Map();
// Populating the map
for (let i = 0; i < N; i++) {
if (M.has(arr[i] & X)) {
M.set(arr[i] & X, M.get(arr[i] & X) + 1);
} else {
M.set(arr[i] & X, 1);
}
}
// Count number of pairs for every
// element in map using mathematical
// concept of combination
for (let m of M) {
let p = m[1];
// As nC2 = n*(n-1)/2
count += (p * (p - 1)) / 2;
}
// Return the resultant count
return count;
}
// Driver Code
let arr = [3, 2, 5, 4, 6, 7];
let X = 6;
let N = arr.length;
document.write(countOfPairs(arr, N, X));
// This code is contributed by gfgking.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ratulmaity2504 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA