Dada una array arr[] que consta de N enteros no negativos y un entero M , la tarea es encontrar el recuento de pares no ordenados {X, Y} de elementos de array que satisfagan la condición setBits(X ⊕ Y) + 2 * setBits (X & Y) = M , donde ⊕ denota el XOR bit a bit y & denota el AND bit a bit .
Ejemplos:
Entrada: arr[] = {30, 0, 4, 5 }, M = 2
Salida: 2
Explicación: Los pares que cumplen las condiciones necesarias son {{3, 0}, {0, 5}}.Entrada: arr[] = {1, 2, 3, 4}, M = 3
Salida: 3
Explicación: Los pares que cumplen las condiciones necesarias son {{1, 3}, {2, 3}, {3, 4}} .
Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles a partir de la array dada y, para cada par, verificar si la condición necesaria se cumple o no. Incremente el conteo de pares que satisfagan las condiciones dadas y, finalmente, imprima el conteo de pares.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- De la propiedad de Bitwise XOR :
- conjuntoBits( a⊕ b ) = conjuntoBits( a|b ) – conjuntoBits( a&b )
- conjuntoBits(a|b) = conjuntoBits(a) + conjuntoBits(b) – conjuntoBits(a&b)
- Por lo tanto, la ecuación dada se convierte en:
- ( conjuntoBits( X|Y ) – conjuntoBits( X&Y ) )+( 2 × conjuntoBits( X&Y ) ) = M
- fijarBits( X ) + fijarBits ( Y ) – fijarBits( X&Y ) – fijarBits( X&Y ) + ( 2 × fijarBits ( X&Y ) ) = M
- conjuntoBits( X ) + conjuntoBits( Y ) = M
- Por lo tanto, la tarea se reduce a contar los pares de elementos cuya suma de bits establecidos es igual a M.
Siga los pasos a continuación para resolver el problema:
- Primero, recorra la array arr[].
- Para cada elemento de array arr[i], actualice arr[i] con el recuento de bits establecidos presentes en él .
- Ahora imprime el conteo de pares de la array cuya suma es igual a M.
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 count number
// of setbits in the number n
int countsetbits(int n)
{
// Stores the count of setbits
int count = 0;
// Iterate while N is
// greater than 0
while (n) {
// Increment count by 1
// if N is odd
count += n & 1;
// Right shift N
n >>= 1;
}
// Return the count of set bits
return (count);
}
// Function to find total count of
// given pairs satisfying the equation
int countPairs(int a[], int N, int M)
{
for (int i = 0; i < N; i++) {
// Update arr[i] with the count
// of set bits of arr[i]
a[i] = countsetbits(a[i]);
}
// Stores the frequency
// of each array element
unordered_map<int, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
// Increment the count
// of arr[i] in mp
mp[a[i]]++;
}
// Stores the total count of pairs
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Increment count by mp[M - a[i]]
count += mp[M - a[i]];
// If a[i] is equal to M-a[i]
if (a[i] == M - a[i]) {
// Decrement count by 1
count--;
}
}
// Return count/2
return (count / 2);
}
// Driver Code
int main()
{
// Input
int arr[] = { 3, 0, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = 2;
cout << countPairs(arr, N, M);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to count number
// of setbits in the number n
static int countsetbits(int n)
{
// Stores the count of setbits
int count = 0;
// Iterate while N is
// greater than 0
while (n != 0)
{
// Increment count by 1
// if N is odd
count += n & 1;
// Right shift N
n >>= 1;
}
// Return the count of set bits
return (count);
}
// Function to find total count of
// given pairs satisfying the equation
static int countPairs(int[] a, int N, int M)
{
for(int i = 0; i < N; i++)
{
// Update arr[i] with the count
// of set bits of arr[i]
a[i] = countsetbits(a[i]);
}
// Stores the frequency
// of each array element
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the array
for (int i = 0; i < N; i++)
{
if (mp.containsKey(a[i]))
{
mp.put(a[i], mp.get(a[i]) + 1);
}
else
{
mp.put(a[i], 1);
}
}
// Stores the total count of pairs
int count = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Increment count by mp[M - a[i]]
count += mp.get(M - a[i]);
// If a[i] is equal to M-a[i]
if (a[i] == M - a[i])
{
// Decrement count by 1
count--;
}
}
// Return count/2
return (count / 2);
}
// Driver Code
public static void main(String[] args)
{
// Input
int[] arr = { 3, 0, 4, 5 };
int N = arr.length;
int M = 2;
System.out.println(countPairs(arr, N, M));
}
}
// This code is contributed by avijitmondal1998
Python3
# Python3 Program for the above approach
# Function to count number
# of setbits in the number n
def countSetBits(n):
# Stores the count of setbits
count = 0
# Iterate while N is
# greater than 0
while (n):
# Increment count by 1
# if N is odd
count += n & 1
# Right shift N
n >>= 1
# Return the count of set bits
return count
def countPairs(arr, N, M):
for i in range(0, N):
# Update arr[i] with the count
# of set bits of arr[i]
arr[i] = countSetBits(arr[i])
# Store counts of all elements in a dictionary
mp = {}
for i in range(0, N):
if arr[i] in mp:
mp[arr[i]] += 1
else:
mp[arr[i]] = 1
twice_count = 0
# Iterate through each element and increment
# the count (Notice that every pair is
# counted twice)
for i in range(0, N):
if M - arr[i] in mp.keys():
twice_count += mp[M - arr[i]]
# if (arr[i], arr[i]) pair satisfies the
# condition, then we need to ensure that
# the count is decreased by one such
# that the (arr[i], arr[i]) pair is not
# considered
if (M - arr[i] == arr[i]):
twice_count -= 1
# return the half of twice_count
return int(twice_count / 2)
# Driver code
# Input
arr = [ 3, 0, 4, 5]
N = len(arr)
M = 2
print(countPairs(arr, N, M))
# This code is contributed by santhoshcharan.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count number
// of setbits in the number n
static int countsetbits(int n)
{
// Stores the count of setbits
int count = 0;
// Iterate while N is
// greater than 0
while (n != 0)
{
// Increment count by 1
// if N is odd
count += n & 1;
// Right shift N
n >>= 1;
}
// Return the count of set bits
return (count);
}
// Function to find total count of
// given pairs satisfying the equation
static int countPairs(int[] a, int N, int M)
{
for(int i = 0; i < N; i++)
{
// Update arr[i] with the count
// of set bits of arr[i]
a[i] = countsetbits(a[i]);
}
// Stores the frequency
// of each array element
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < N; ++i)
{
// Update frequency of
// each array element
if (mp.ContainsKey(a[i]) == true)
mp[a[i]] += 1;
else
mp[a[i]] = 1;
}
// Stores the total count of pairs
int count = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Increment count by mp[M - a[i]]
count += mp[M - a[i]];
// If a[i] is equal to M-a[i]
if (a[i] == M - a[i])
{
// Decrement count by 1
count--;
}
}
// Return count/2
return (count / 2);
}
// Driver Code
static public void Main()
{
// Input
int[] arr = { 3, 0, 4, 5 };
int N = arr.Length;
int M = 2;
Console.WriteLine(countPairs(arr, N, M));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to count number
// of setbits in the number n
function countsetbits(n)
{
// Stores the count of setbits
var count = 0;
// Iterate while N is
// greater than 0
while (n) {
// Increment count by 1
// if N is odd
count += n & 1;
// Right shift N
n >>= 1;
}
// Return the count of set bits
return (count);
}
// Function to find total count of
// given pairs satisfying the equation
function countPairs(a, N, M)
{
for (var i = 0; i < N; i++) {
// Update arr[i] with the count
// of set bits of arr[i]
a[i] = countsetbits(a[i]);
}
// Stores the frequency
// of each array element
var mp = new Map();
// Traverse the array
for (var i = 0; i < N; i++) {
// Increment the count
// of arr[i] in mp
if(mp.has(a[i]))
mp.set(a[i], mp.get(a[i])+1)
else
mp.set(a[i], 1)
}
// Stores the total count of pairs
var count = 0;
// Traverse the array arr[]
for (var i = 0; i < N; i++) {
// Increment count by mp[M - a[i]]
count += mp.get(M - a[i]);
// If a[i] is equal to M-a[i]
if (a[i] == M - a[i]) {
// Decrement count by 1
count--;
}
}
// Return count/2
return (count / 2);
}
// Driver Code
// Input
var arr = [3, 0, 4, 5];
var N = arr.length;
var M = 2;
document.write( countPairs(arr, N, M));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por santhoshcharan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA