Dada una array arr[] que consta de N enteros, la tarea es encontrar el recuento de pares no ordenados en la array dada cuya suma contiene todos los bits establecidos.
Ejemplos:
Entrada: arr[] = {1, 2, 5}
Salida: 2
Explicación: Los posibles pares que satisfacen las condiciones son:
- (1, 2): 1 + 2 = 3 (11) todos los bits se establecen en representación binaria de 3.
- 2) (2, 5): 2 + 5 = 7 (111) todos los bits se establecen en representación binaria de 7.
Por lo tanto, la cuenta es 2.
Entrada: arr[] = {1, 2, 5, 10}
Salida: 3
Explicación: Los posibles pares que satisfacen las condiciones son:
- (1, 2): 1 + 2 = 3 (11) todos los bits se establecen en representación binaria de 3.
- (2, 5): 2 + 5 = 7 (111) todos los bits se establecen en representación binaria de 7.
- (5, 10): 5 + 10 = 15 (1111) todos los bits se establecen en representación binaria de 15.
Enfoque ingenuo: la idea es generar todos los pares posibles y verificar si su suma tiene todos los bits configurados o no . Si se encuentra que es cierto, entonces cuente ese par en el conteo resultante. Imprime el conteo después de verificar todos los pares.
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 check if the number num
// has all set bits or not
bool allSetBits(int num)
{
// Find total bitsac
int totalBits = log2(num) + 1;
// Find count of set bit
int setBits = __builtin_popcount(num);
// Return true if all bit are set
if (totalBits == setBits)
return true;
else
return false;
}
// Function that find the count of
// pairs whose sum has all set bits
int countPairs(int arr[], int n)
{
// Stores the count of pairs
int ans = 0;
// Generate all the pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Find the sum of current pair
int sum = arr[i] + arr[j];
// If all bits are set
if (allSetBits(sum))
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 5, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to check if the
// number num has all set
// bits or not
static boolean allSetBits(int num)
{
// Find total bitsac
int totalBits = (int)Math.log(num) + 1;
// Find count of set bit
int setBits = Integer.bitCount(num);
// Return true if all
// bit are set
if (totalBits == setBits)
return true;
else
return false;
}
// Function that find the
// count of pairs whose sum
// has all set bits
static int countPairs(int arr[],
int n)
{
// Stores the count
// of pairs
int ans = 0;
// Generate all the pairs
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// Find the sum of
// current pair
int sum = arr[i] + arr[j];
// If all bits are set
if (allSetBits(sum))
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 2, 5, 10};
int N = arr.length;
// Function Call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
from math import log2
# Function to check if the number num
# has all set bits or not
def allSetBits(num):
# Find total bits
totalBits = int(log2(num) + 1)
# Find count of set bit
setBits = bin(num).count('1')
# Return true if all bit are set
if (totalBits == setBits):
return True
else:
return False
# Function that find the count of
# pairs whose sum has all set bits
def countPairs(arr, n):
# Stores the count of pairs
ans = 0
# Generate all the pairs
for i in range(n):
for j in range(i + 1, n):
# Find the sum of current pair
sum = arr[i] + arr[j]
# If all bits are set
if (allSetBits(sum)):
ans += 1
# Return the final count
return ans
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 5, 10 ]
N = len(arr)
# Function Call
print(countPairs(arr, N))
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to check if the
// number num has all set
// bits or not
static bool allSetBits(int num)
{
// Find total bitsac
int totalBits = (int)Math.Log(num) + 1;
// Find count of set bit
int setBits = countSetBits(num);
// Return true if all
// bit are set
if (totalBits == setBits)
return true;
else
return false;
}
// Function that find the
// count of pairs whose sum
// has all set bits
static int countPairs(int []arr,
int n)
{
// Stores the count
// of pairs
int ans = 0;
// Generate all the pairs
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// Find the sum of
// current pair
int sum = arr[i] + arr[j];
// If all bits are set
if (allSetBits(sum))
ans++;
}
}
// Return the readonly count
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 2, 5, 10};
int N = arr.Length;
// Function Call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the
// above approach
function countSetBits(n)
{
let count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to check if the
// number num has all set
// bits or not
function allSetBits(num)
{
// Find total bitsac
let totalBits = Math.floor(Math.log(num)) + 1;
// Find count of set bit
let setBits = countSetBits(num);
// Return true if all
// bit are set
if (totalBits == setBits)
return true;
else
return false;
}
// Function that find the
// count of pairs whose sum
// has all set bits
function countPairs(arr, n)
{
// Stores the count
// of pairs
let ans = 0;
// Generate all the pairs
for(let i = 0; i < n; i++)
{
for(let j = i + 1; j < n; j++)
{
// Find the sum of
// current pair
let sum = arr[i] + arr[j];
// If all bits are set
if (allSetBits(sum))
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
let arr = [ 1, 2, 5, 10 ];
let N = arr.length;
// Function Call
document.write(countPairs(arr, N));
// This code is contributed by souravghosh0416
</script>
Producción
3
Complejidad de tiempo: O(N 2 log N), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)
Enfoque eficiente: la observación clave es que solo hay números de registro N de 0 a N que contienen todos los bits establecidos. Esta propiedad se puede utilizar para optimizar el enfoque anterior. Siga los pasos a continuación para resolver el problema:
- Almacene todos los elementos log(MAX_INTEGER) en una array setArray[] .
- Mapee todos los elementos de la array arr[] en una estructura de datos Map donde un elemento es una clave y su frecuencia es el valor.
- Recorra la array dada arr[] sobre el rango [0, N – 1] y en bucle anidado recorra la array setArray[] desde j = 0 hasta log(MAX_INTEGER) e incremente ans por map[setArray[j] – arr[i ]] donde ans almacena el número total de pares requeridos.
- Como hay doble conteo porque (a, b) y (b, a) se cuentan dos veces. Por lo tanto, imprima el valor de ans/2 para obtener el conteo requerido.
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;
// Store numbers having all set bits
vector<int> setArray;
// Store frequency of values in arr[]
map<int, int> mp;
// Function to fill setArray[] with
// numbers that have all set bits
void fillsetArray()
{
for (int i = 1; i < 31; i++) {
setArray.push_back((1 << i) - 1);
}
}
// Function to find the count of pairs
// whose sum contains all set bits
int countPairs(int arr[], int n)
{
// Stores the count of pairs
int ans = 0;
fillsetArray();
// Hash the values of arr[] in mp
for (int i = 0; i < n; i++)
mp[arr[i]]++;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Iterate over the range [0, 30]
for (int j = 0; j < 30; j++) {
// Find the difference
int value = setArray[j] - arr[i];
// Update the final count
ans += mp[value];
}
}
// Return the final count
return ans / 2;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 5, 10 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Store numbers having
// all set bits
static Vector<Integer> setArray =
new Vector<>();
// Store frequency of
// values in arr[]
static HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Function to fill setArray[]
// with numbers that have all
// set bits
static void fillsetArray()
{
for (int i = 1; i < 31; i++)
{
setArray.add((1 << i) - 1);
}
}
// Function to find the count
// of pairs whose sum contains
// all set bits
static int countPairs(int arr[],
int n)
{
// Stores the count
// of pairs
int ans = 0;
fillsetArray();
// Hash the values of
// arr[] in mp
for (int i = 0; i < n; i++)
if(mp.containsKey(arr[i]))
{
mp.put(arr[i],
mp.get(arr[i]) + 1);
}
else
{
mp.put(arr[i], 1);
}
// Traverse the array arr[]
for (int i = 0; i < n; i++)
{
// Iterate over the range
// [0, 30]
for (int j = 0; j < 30; j++)
{
// Find the difference
int value = setArray.get(j) -
arr[i];
// Update the final count
if(mp.containsKey(value))
ans += mp.get(value);
}
}
// Return the final count
return ans / 2;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 2, 5, 10};
int N = arr.length;
// Function Call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the # above approach from collections import defaultdict # Store numbers having # all set bits setArray = [] # Store frequency of values # in arr[] mp = defaultdict (int) # Function to fill setArray[] with # numbers that have all set bits def fillsetArray(): for i in range (1, 31): setArray.append((1 << i) - 1) # Function to find the # count of pairs whose sum # contains all set bits def countPairs(arr, n): # Stores the count of pairs ans = 0 fillsetArray() # Hash the values of # arr[] in mp for i in range (n): mp[arr[i]] += 1 # Traverse the array arr[] for i in range (n): # Iterate over the range # [0, 30] for j in range (30): # Find the difference value = setArray[j] - arr[i] # Update the final count ans += mp[value] # Return the final count return ans // 2 # Driver Code if __name__ == "__main__": arr = [1, 2, 5, 10] N = len(arr) # Function Call print (countPairs(arr, N)) # This code is contributed by Chitranayal
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Store numbers having
// all set bits
static List<int> setArray = new List<int>();
// Store frequency of
// values in []arr
static Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Function to fill setArray[]
// with numbers that have all
// set bits
static void fillsetArray()
{
for(int i = 1; i < 31; i++)
{
setArray.Add((1 << i) - 1);
}
}
// Function to find the count
// of pairs whose sum contains
// all set bits
static int countPairs(int []arr,
int n)
{
// Stores the count
// of pairs
int ans = 0;
fillsetArray();
// Hash the values of
// []arr in mp
for(int i = 0; i < n; i++)
if(mp.ContainsKey(arr[i]))
{
mp.Add(arr[i],
mp[arr[i]] + 1);
}
else
{
mp.Add(arr[i], 1);
}
// Traverse the array []arr
for(int i = 0; i < n; i++)
{
// Iterate over the range
// [0, 30]
for(int j = 0; j < 30; j++)
{
// Find the difference
int value = setArray[j] -
arr[i];
// Update the readonly count
if (mp.ContainsKey(value))
ans += mp[value];
}
}
// Return the readonly count
return ans / 2;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 2, 5, 10};
int N = arr.Length;
// Function Call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// js program for the above approach
// Store numbers having all set bits
let setArray = [];
// Store frequency of values in arr[]
let mp = new Map;
// Function to fill setArray[] with
// numbers that have all set bits
function fillsetArray()
{
for (let i = 1; i < 31; i++) {
setArray.push((1 << i) - 1);
}
return setArray;
}
// Function to find the count of pairs
// whose sum contains all set bits
function countPairs( arr, n)
{
// Stores the count of pairs
let ans = 0;
setArray = fillsetArray();
// Hash the values of arr[] in mp
for (let i = 0; i < n; i++){
if(mp[arr[i]])
mp[arr[i]]++;
else
mp[arr[i]] = 1
}
// Traverse the array arr[]
for (let i = 0; i < n; i++) {
// Iterate over the range [0, 30]
for (let j = 0; j < 30; j++) {
// Find the difference
let value = setArray[j] - arr[i];
// Update the final count
if(mp[value])
ans += mp[value];
}
}
// Return the final count
return Math.floor(ans / 2);
}
// Driver Code
let Arr = [ 1, 2, 5, 10 ];
let N = Arr.length;
// Function Call
document.write(countPairs(Arr, N));
</script>
Producción
3
Complejidad de tiempo: O(N*32), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA