Dada una array de tamaño n y un número entero k, cuente todos los pares en la array que difieren exactamente en K bits de representación binaria de ambos números.
Las arrays de entrada tienen elementos con valores pequeños y posiblemente muchas repeticiones.
Ejemplos:
Input: arr[] = {2, 4, 1, 3, 1}
k = 2
Output: 5
Explanation:
There are only 4 pairs which differs in
exactly 2 bits of binary representation:
(2, 4), (1, 2) [Two times] and (4, 1)
[Two times]
Input : arr[] = {2, 1, 2, 1}
k = 2
Output : 4
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Enfoque ingenuo
Una fuerza bruta consiste en ejecutar los dos bucles uno dentro del otro y seleccionar los pares uno por uno y tomar un XOR de ambos elementos. El resultado del valor XORed contiene un conjunto de bits que difieren en ambos elementos. Ahora solo necesitamos contar los bits establecidos totales para compararlos con el valor K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count all pairs with bit difference
// as k
#include<bits/stdc++.h>
using namespace std;
// Utility function to count total ones in a number
int bitCount(int n)
{
int count = 0;
while (n)
{
if (n & 1)
++count;
n >>= 1;
}
return count;
}
// Function to count pairs of K different bits
long long countPairsWithKDiff(int arr[], int n, int k)
{
long long ans = 0; // initialize final answer
for (int i = 0; i < n-1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int xoredNum = arr[i] ^ arr[j];
// Check for K differ bit
if (k == bitCount(xoredNum))
++ans;
}
}
return ans;
}
// Driver code
int main()
{
int k = 2;
int arr[] = {2, 4, 1, 3, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Total pairs for k = " << k << " are "
<< countPairsWithKDiff(arr, n, k) << "\n";
return 0;
}
Java
// Java program to count all pairs with bit difference
// as k
import java.io.*;
class GFG {
// Utility function to count total ones in a number
static int bitCount(int n)
{
int count = 0;
while (n>0)
{
if ((n & 1)>0)
++count;
n >>= 1;
}
return count;
}
// Function to count pairs of K different bits
static long countPairsWithKDiff(int arr[], int n, int k)
{
long ans = 0; // initialize final answer
for (int i = 0; i < n-1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int xoredNum = arr[i] ^ arr[j];
// Check for K differ bit
if (k == bitCount(xoredNum))
++ans;
}
}
return ans;
}
// Driver code
public static void main (String[] args) {
int k = 2;
int arr[] = {2, 4, 1, 3, 1};
int n =arr.length;
System.out.println( "Total pairs for k = " + k + " are "
+ countPairsWithKDiff(arr, n, k) + "\n");
}
}
// This code is contributed by shs..
Python3
# Python 3 program to count all pairs
# with bit difference as k
# Utility function to count total
# ones in a number
def bitCount(n):
count = 0
while (n):
if (n & 1):
count += 1
n >>= 1
return count
# Function to count pairs of K different bits
def countPairsWithKDiff(arr, n, k):
ans = 0
# initialize final answer
for i in range(0, n - 1, 1):
for j in range(i + 1, n, 1):
xoredNum = arr[i] ^ arr[j]
# Check for K differ bit
if (k == bitCount(xoredNum)):
ans += 1
return ans
# Driver code
if __name__ == '__main__':
k = 2
arr = [2, 4, 1, 3, 1]
n = len(arr)
print("Total pairs for k =", k, "are",
countPairsWithKDiff(arr, n, k))
# This code is contributed by
# Sanjit_Prasad
C#
// C# program to count all pairs
// with bit difference as k
using System;
class GFG
{
// Utility function to count
// total ones in a number
static int bitCount(int n)
{
int count = 0;
while (n > 0)
{
if ((n & 1) > 0)
++count;
n >>= 1;
}
return count;
}
// Function to count pairs of K different bits
static long countPairsWithKDiff(int []arr,
int n, int k)
{
long ans = 0; // initialize final answer
for (int i = 0; i < n-1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int xoredNum = arr[i] ^ arr[j];
// Check for K differ bit
if (k == bitCount(xoredNum))
++ans;
}
}
return ans;
}
// Driver code
public static void Main ()
{
int k = 2;
int []arr = {2, 4, 1, 3, 1};
int n = arr.Length;
Console.WriteLine( "Total pairs for k = " +
k + " are " +
countPairsWithKDiff(arr, n, k) + "\n");
}
}
// This code is contributed by shs..
PHP
<?php
// PHP program to count all
// pairs with bit difference
// as k
// Utility function to count
// total ones in a number
function bitCount($n)
{
$count = 0;
while ($n)
{
if ($n & 1)
++$count;
$n >>= 1;
}
return $count;
}
// Function to count pairs
// of K different bits
function countPairsWithKDiff($arr, $n, $k)
{
// initialize final answer
$ans = 0;
for ($i = 0; $i < $n-1; ++$i)
{
for ($j = $i + 1; $j < $n; ++$j)
{
$xoredNum = $arr[$i] ^ $arr[$j];
// Check for K differ bit
if ($k == bitCount($xoredNum))
++$ans;
}
}
return $ans;
}
// Driver code
$k = 2;
$arr = array(2, 4, 1, 3, 1);
$n = count($arr);
echo "Total pairs for k = " , $k , " are "
, countPairsWithKDiff($arr, $n, $k) , "\n";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to count all pairs with bit difference
// as k
// Utility function to count total ones in a number
function bitCount(n)
{
let count = 0;
while (n>0)
{
if ((n & 1)>0)
++count;
n >>= 1;
}
return count;
}
// Function to count pairs of K different bits
function countPairsWithKDiff(arr, n, k)
{
let ans = 0; // initialize final answer
for (let i = 0; i < n-1; ++i)
{
for (let j = i + 1; j < n; ++j)
{
let xoredNum = arr[i] ^ arr[j];
// Check for K differ bit
if (k == bitCount(xoredNum))
++ans;
}
}
return ans;
}
// Driver Code
let k = 2;
let arr = [2, 4, 1, 3, 1];
let n = arr.length;
document.write( "Total pairs for k = " + k + " are "
+ countPairsWithKDiff(arr, n, k) + "\n");
</script>
Producción:
Total pairs for k = 2 are 5
Complejidad de tiempo: O (N 2 * log MAX) donde MAX es el elemento máximo en la array de entrada.
Espacio auxiliar: O(1)
Enfoque eficiente
Este enfoque es eficiente para los casos en que la array de entrada tiene elementos pequeños y posiblemente muchas repeticiones. La idea es iterar de 0 a max(arr[i]) y para cada par (i, j) verificar el número de bits establecidos en (i ^ j) y comparar esto con K. Podemos usar la función incorporada de gcc( __builtin_popcount ) o precalcule dicha array para que la verificación sea más rápida. Si el número de unos en i ^ j es igual a K, sumaremos el recuento total de i y j.
C++
// Below is C++ approach of finding total k bit
// difference pairs
#include<bits/stdc++.h>
using namespace std;
// Function to calculate K bit different pairs in array
long long kBitDifferencePairs(int arr[], int n, int k)
{
// Get the maximum value among all array elements
int MAX = *max_element(arr, arr+n);
// Set the count array to 0, count[] stores the
// total frequency of array elements
long long count[MAX+1];
memset(count, 0, sizeof(count));
for (int i=0; i < n; ++i)
++count[arr[i]];
// Initialize result
long long ans = 0;
// For 0 bit answer will be total count of same number
if (k == 0)
{
for (int i = 0; i <= MAX; ++i)
ans += (count[i] * (count[i] - 1)) / 2;
return ans;
}
for (int i = 0; i <= MAX; ++i)
{
// if count[i] is 0, skip the next loop as it
// will not contribute the answer
if (!count[i])
continue;
for (int j = i + 1; j <= MAX; ++j)
{
//Update answer if k differ bit found
if ( __builtin_popcount(i ^ j) == k)
ans += count[i] * count[j];
}
}
return ans;
}
// Driver code
int main()
{
int k = 2;
int arr[] = {2, 4, 1, 3, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Total pairs for k = " << k << " are = "
<< kBitDifferencePairs(arr, n, k) << "\n";
k = 3;
cout << "Total pairs for k = " << k << " are = "
<< kBitDifferencePairs(arr, n, k) ;
return 0;
}
Java
// Below is Java approach of finding total k bit
// difference pairs
import java.util.*;
class GFG
{
// Function to calculate K bit
// different pairs in array
static long kBitDifferencePairs(int arr[],
int n, int k)
{
// Get the maximum value among all array elements
int MAX = Arrays.stream(arr).max().getAsInt();
// Set the count array to 0,
// count[] stores the total
// frequency of array elements
long []count = new long[MAX + 1];
Arrays.fill(count, 0);
for (int i = 0; i < n; ++i)
++count[arr[i]];
// Initialize result
long ans = 0;
// For 0 bit answer will be total
// count of same number
if (k == 0)
{
for (int i = 0; i <= MAX; ++i)
ans += (count[i] * (count[i] - 1)) / 2;
return ans;
}
for (int i = 0; i <= MAX; ++i)
{
// if count[i] is 0, skip the next loop
// as it will not contribute the answer
if (count[i] == 0)
continue;
for (int j = i + 1; j <= MAX; ++j)
{
// Update answer if k differ bit found
if ( Integer.bitCount(i ^ j) == k)
ans += count[i] * count[j];
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int k = 2;
int arr[] = {2, 4, 1, 3, 1};
int n = arr.length;
System.out.println("Total pairs for k = " +
k + " are = " +
kBitDifferencePairs(arr, n, k));
k = 3;
System.out.println("Total pairs for k = " +
k + " are = " +
kBitDifferencePairs(arr, n, k));
}
}
// This code is contributed by Rajput-Ji
Python3
# Below is Python3 approach of finding
# total k bit difference pairs
# Function to calculate K bit different
# pairs in array
def kBitDifferencePairs(arr, n, k):
# Get the maximum value among
# all array elements
MAX = max(arr)
# Set the count array to 0, count[] stores
# the total frequency of array elements
count = [0 for i in range(MAX + 1)]
for i in range(n):
count[arr[i]] += 1
# Initialize result
ans = 0
# For 0 bit answer will be total
# count of same number
if (k == 0):
for i in range(MAX + 1):
ans += (count[i] * (count[i] - 1)) // 2
return ans
for i in range(MAX + 1):
# if count[i] is 0, skip the next loop
# as it will not contribute the answer
if (count[i] == 0):
continue
for j in range(i + 1, MAX + 1):
# Update answer if k differ bit found
if (bin(i ^ j).count('1') == k):
ans += count[i] * count[j]
return ans
# Driver code
k = 2
arr = [2, 4, 1, 3, 1]
n = len(arr)
print("Total pairs for k =", k, "are",
kBitDifferencePairs(arr, n, k))
k = 3
print("Total pairs for k =", k, "are",
kBitDifferencePairs(arr, n, k))
# This code is contributed by mohit kumar
C#
// Below is C# approach of finding
// total k bit difference pairs
using System;
using System.Linq;
class GFG
{
// Function to calculate K bit
// different pairs in array
static long kBitDifferencePairs(int []arr,
int n, int k)
{
// Get the maximum value among
// all array elements
int MAX = arr.Max();
// Set the count array to 0,
// count[] stores the total
// frequency of array elements
long []count = new long[MAX + 1];
for (int i = 0; i < n; ++i)
++count[arr[i]];
// Initialize result
long ans = 0;
// For 0 bit answer will be total
// count of same number
if (k == 0)
{
for (int i = 0; i <= MAX; ++i)
ans += (count[i] *
(count[i] - 1)) / 2;
return ans;
}
for (int i = 0; i <= MAX; ++i)
{
// if count[i] is 0, skip the next loop
// as it will not contribute the answer
if (count[i] == 0)
continue;
for (int j = i + 1; j <= MAX; ++j)
{
// Update answer if k differ bit found
if (BitCount(i ^ j) == k)
ans += count[i] * count[j];
}
}
return ans;
}
static int BitCount(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int k = 2;
int []arr = {2, 4, 1, 3, 1};
int n = arr.Length;
Console.WriteLine("Total pairs for k = " +
k + " are = " +
kBitDifferencePairs(arr, n, k));
k = 3;
Console.WriteLine("Total pairs for k = " +
k + " are = " +
kBitDifferencePairs(arr, n, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Below is Javascript approach
// of finding total k bit
// difference pairs
// Function to calculate K bit
// different pairs in array
function kBitDifferencePairs(arr, n, k)
{
// Get the maximum value among
// all array elements
let MAX = Math.max(...arr);
// Set the count array to 0, count[] stores the
// total frequency of array elements
let count = new Array(MAX+1).fill(0);
for (let i=0; i < n; ++i)
++count[arr[i]];
// Initialize result
let ans = 0;
// For 0 bit answer will be total
// count of same number
if (k == 0)
{
for (let i = 0; i <= MAX; ++i)
ans += parseInt((count[i] *
(count[i] - 1)) / 2);
return ans;
}
for (let i = 0; i <= MAX; ++i)
{
// if count[i] is 0, skip
// the next loop as it
// will not contribute the answer
if (!count[i])
continue;
for (let j = i + 1; j <= MAX; ++j)
{
//Update answer if k differ bit found
if ( BitCount(i ^ j) == k)
ans += count[i] * count[j];
}
}
return ans;
}
function BitCount(n)
{
let count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Driver code
let k = 2;
let arr = [2, 4, 1, 3, 1];
let n = arr.length;
document.write("Total pairs for k = " + k + " are = "
+ kBitDifferencePairs(arr, n, k) + "<br>");
k = 3;
document.write("Total pairs for k = " + k + " are = "
+ kBitDifferencePairs(arr, n, k) + "<br>");
</script>
Producción:
Total pairs for k = 2 are = 5
Complejidad de tiempo: O(MAX 2 ) donde MAX es el elemento máximo en la array de entrada.
Espacio auxiliar: O(MAX)
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA