Dada una array arr[] , la tarea es contar todos los pares válidos de la array. Se dice que un par (arr[i], arr[j]) es válido si func( arr[i] ) + func( arr[j] ) = func( XOR(arr[i], arr[j]) ) donde func(x) devuelve el número de bits establecidos en x .
Ejemplos:
Entrada: arr[] = {2, 3, 4, 5, 6}
Salida: 3
(2, 4), (2, 5) y (3, 4) son los únicos pares válidos.Entrada: arr[] = {12, 13, 34, 25, 6}
Salida: 4
Enfoque: iterar todos los pares posibles y verificar si el par satisface la condición dada. Si se cumple la condición, actualice count = count + 1 . Imprime el conteo al final.
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 return the number
// of set bits in n
int setBits(int n)
{
int count = 0;
while (n) {
n = n & (n - 1);
count++;
}
return count;
}
// Function to return the count of required pairs
int countPairs(int a[], int n)
{
int count = 0;
for (int i = 0; i < n - 1; i++) {
// Set bits for first element of the pair
int setbits_x = setBits(a[i]);
for (int j = i + 1; j < n; j++) {
// Set bits for second element of the pair
int setbits_y = setBits(a[j]);
// Set bits of the resultant number which is
// the XOR of both the elements of the pair
int setbits_xor_xy = setBits(a[i] ^ a[j]);
// If the condition is satisfied
if (setbits_x + setbits_y == setbits_xor_xy)
// Increment the count
count++;
}
}
// Return the total count
return count;
}
// Driver code
int main()
{
int a[] = { 2, 3, 4, 5, 6 };
int n = sizeof(a) / sizeof(a[0]);
cout << countPairs(a, n);
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
// Function to return the number
// of set bits in n
static int setBits(int n)
{
int count = 0;
while (n > 0)
{
n = n & (n - 1);
count++;
}
return count;
}
// Function to return the count of
// required pairs
static int countPairs(int a[], int n)
{
int count = 0;
for (int i = 0; i < n - 1; i++)
{
// Set bits for first element
// of the pair
int setbits_x = setBits(a[i]);
for (int j = i + 1; j < n; j++)
{
// Set bits for second element
// of the pair
int setbits_y = setBits(a[j]);
// Set bits of the resultant number which is
// the XOR of both the elements of the pair
int setbits_xor_xy = setBits(a[i] ^ a[j]);
// If the condition is satisfied
if (setbits_x + setbits_y == setbits_xor_xy)
// Increment the count
count++;
}
}
// Return the total count
return count;
}
// Driver code
public static void main (String[] args)
{
int []a = { 2, 3, 4, 5, 6 };
int n = a.length;
System.out.println(countPairs(a, n));
}
}
// This code is contributed by ajit.
Python3
# Python 3 implementation of the approach # Function to return the number # of set bits in n def setBits(n): count = 0 while (n): n = n & (n - 1) count += 1 return count # Function to return the count # of required pairs def countPairs(a, n): count = 0 for i in range(0, n - 1, 1): # Set bits for first element # of the pair setbits_x = setBits(a[i]) for j in range(i + 1, n, 1): # Set bits for second element # of the pair setbits_y = setBits(a[j]) # Set bits of the resultant number # which is the XOR of both the # elements of the pair setbits_xor_xy = setBits(a[i] ^ a[j]); # If the condition is satisfied if (setbits_x + setbits_y == setbits_xor_xy): # Increment the count count += 1 # Return the total count return count # Driver code if __name__ == '__main__': a = [2, 3, 4, 5, 6] n = len(a) print(countPairs(a, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number
// of set bits in n
static int setBits(int n)
{
int count = 0;
while (n > 0)
{
n = n & (n - 1);
count++;
}
return count;
}
// Function to return the count of
// required pairs
static int countPairs(int []a, int n)
{
int count = 0;
for (int i = 0; i < n - 1; i++)
{
// Set bits for first element
// of the pair
int setbits_x = setBits(a[i]);
for (int j = i + 1; j < n; j++)
{
// Set bits for second element
// of the pair
int setbits_y = setBits(a[j]);
// Set bits of the resultant number which is
// the XOR of both the elements of the pair
int setbits_xor_xy = setBits(a[i] ^ a[j]);
// If the condition is satisfied
if (setbits_x + setbits_y == setbits_xor_xy)
// Increment the count
count++;
}
}
// Return the total count
return count;
}
// Driver code
public static void Main()
{
int []a = { 2, 3, 4, 5, 6 };
int n = a.Length;
Console.Write(countPairs(a, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to return the number
// of set bits in n
function setBits($n)
{
$count = 0;
while ($n)
{
$n = $n & ($n - 1);
$count++;
}
return $count;
}
// Function to return the count of
// required pairs
function countPairs(&$a, $n)
{
$count = 0;
for ($i = 0; $i < $n - 1; $i++)
{
// Set bits for first element
// of the pair
$setbits_x = setBits($a[$i]);
for ($j = $i + 1; $j < $n; $j++)
{
// Set bits for second element of the pair
$setbits_y = setBits($a[$j]);
// Set bits of the resultant number which is
// the XOR of both the elements of the pair
$setbits_xor_xy = setBits($a[$i] ^ $a[$j]);
// If the condition is satisfied
if ($setbits_x +
$setbits_y == $setbits_xor_xy)
// Increment the count
$count++;
}
}
// Return the total count
return $count;
}
// Driver code
$a = array(2, 3, 4, 5, 6 );
$n = sizeof($a) / sizeof($a[0]);
echo countPairs($a, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the number
// of set bits in n
function setBits(n)
{
let count = 0;
while (n > 0)
{
n = n & (n - 1);
count++;
}
return count;
}
// Function to return the count of
// required pairs
function countPairs(a, n)
{
let count = 0;
for(let i = 0; i < n - 1; i++)
{
// Set bits for first element
// of the pair
let setbits_x = setBits(a[i]);
for(let j = i + 1; j < n; j++)
{
// Set bits for second element
// of the pair
let setbits_y = setBits(a[j]);
// Set bits of the resultant number which is
// the XOR of both the elements of the pair
let setbits_xor_xy = setBits(a[i] ^ a[j]);
// If the condition is satisfied
if (setbits_x + setbits_y == setbits_xor_xy)
// Increment the count
count++;
}
}
// Return the total count
return count;
}
// Driver code
let a = [ 2, 3, 4, 5, 6 ];
let n = a.length;
document.write(countPairs(a, n));
// This code is contributed by unknown2108
</script>
Producción:
3
Complejidad de tiempo: O(N 2 logM), donde N es el tamaño de la array dada y M es el elemento máximo en la array.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA