Dada una array arr que contiene N enteros, la tarea es contar el número posible de pares de elementos con el mismo número de bits establecidos.
Ejemplos:
Entrada: N = 8, arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Salida: 9
Explicación:
Elementos con 1 bit establecido: 1, 2, 4, 8
Elementos con 2 bits establecidos : 3, 5, 6
Elementos con 3 bits establecidos: 7
Por lo tanto, {1, 2}, {1, 4}, {1, 8}, {2, 4}, {2, 8}, {4, 8} , {3, 5}, {3, 6} y {5, 6} son los posibles pares.Entrada: N = 12, arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Salida: 22
Acercarse:
- Calcule previamente y almacene los bits establecidos para todos los números hasta el elemento máximo de la array en bitscount[] . Para todas las potencias de 2, almacene 1 en su índice respectivo. Después de eso, calcule el número de bits establecidos para los elementos restantes mediante la relación:
bitscount[i] = bitscount[potencia anterior de 2] + bitscount[i – potencia anterior de 2]
- Almacene la frecuencia de los bits establecidos en los elementos de la array en un mapa .
- Agregue el número de pares posibles para cada conteo de bits establecido. Si X elementos tienen el mismo número de bits establecidos, el número de pares posibles entre ellos es X * (X – 1) / 2 .
- Imprime el recuento total de dichos pares.
El siguiente código es la implementación del enfoque anterior:
C++14
// C++ Program to count // possible number of pairs // of elements with same // number of set bits. #include <bits/stdc++.h> using namespace std; // Function to return the // count of Pairs int countPairs(int arr[], int N) { // Get the maximum element int maxm = *max_element(arr, arr + N); int i, k; // Array to store count of bits // of all elements upto maxm int bitscount[maxm + 1] = { 0 }; // Store the set bits // for powers of 2 for (i = 1; i <= maxm; i *= 2) bitscount[i] = 1; // Compute the set bits for // the remaining elements for (i = 1; i <= maxm; i++) { if (bitscount[i] == 1) k = i; if (bitscount[i] == 0) { bitscount[i] = bitscount[k] + bitscount[i - k]; } } // Store the frequency // of respective counts // of set bits map<int, int> setbits; for (int i = 0; i < N; i++) { setbits[bitscount[arr[i]]]++; } int ans = 0; for (auto it : setbits) { ans += it.second * (it.second - 1) / 2; } return ans; } int main() { int N = 12; int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; cout << countPairs(arr, N); return 0; }
Java
// Java program to count possible // number of pairs of elements // with same number of set bits import java.util.*; import java.lang.*; class GFG{ // Function to return the // count of Pairs static int countPairs(int []arr, int N) { // Get the maximum element int maxm = arr[0]; for(int j = 1; j < N; j++) { if (maxm < arr[j]) { maxm = arr[j]; } } int i, k = 0; // Array to store count of bits // of all elements upto maxm int[] bitscount = new int[maxm + 1]; Arrays.fill(bitscount, 0); // Store the set bits // for powers of 2 for(i = 1; i <= maxm; i *= 2) bitscount[i] = 1; // Compute the set bits for // the remaining elements for(i = 1; i <= maxm; i++) { if (bitscount[i] == 1) k = i; if (bitscount[i] == 0) { bitscount[i] = bitscount[k] + bitscount[i - k]; } } // Store the frequency // of respective counts // of set bits Map<Integer, Integer> setbits = new HashMap<>(); for(int j = 0; j < N; j++) { setbits.put(bitscount[arr[j]], setbits.getOrDefault( bitscount[arr[j]], 0) + 1); } int ans = 0; for(int it : setbits.values()) { ans += it * (it - 1) / 2; } return ans; } // Driver code public static void main(String[] args) { int N = 12; int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; System.out.println(countPairs(arr, N)); } } // This code is contributed by offbeat
Python3
# Python3 program to count possible number # of pairs of elements with same number # of set bits. # Function to return the # count of Pairs def countPairs(arr, N): # Get the maximum element maxm = max(arr) i = 0 k = 0 # Array to store count of bits # of all elements upto maxm bitscount = [0 for i in range(maxm + 1)] i = 1 # Store the set bits # for powers of 2 while i <= maxm: bitscount[i] = 1 i *= 2 # Compute the set bits for # the remaining elements for i in range(1, maxm + 1): if (bitscount[i] == 1): k = i if (bitscount[i] == 0): bitscount[i] = (bitscount[k] + bitscount[i - k]) # Store the frequency # of respective counts # of set bits setbits = dict() for i in range(N): if bitscount[arr[i]] in setbits: setbits[bitscount[arr[i]]] += 1 else: setbits[bitscount[arr[i]]] = 1 ans = 0 for it in setbits.values(): ans += it * (it - 1) // 2 return ans # Driver Code if __name__=='__main__': N = 12 arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] print(countPairs(arr, N)) # This code is contributed by pratham76
C#
// C# program to count // possible number of pairs // of elements with same // number of set bits. using System; using System.Collections; using System.Collections.Generic; using System.Text; class GFG{ // Function to return the // count of Pairs static int countPairs(int []arr, int N) { // Get the maximum element int maxm = -int.MaxValue; for(int j = 0; j < N; j++) { if (maxm < arr[j]) { maxm = arr[j]; } } int i, k = 0; // Array to store count of bits // of all elements upto maxm int []bitscount = new int[maxm + 1]; Array.Fill(bitscount, 0); // Store the set bits // for powers of 2 for(i = 1; i <= maxm; i *= 2) bitscount[i] = 1; // Compute the set bits for // the remaining elements for(i = 1; i <= maxm; i++) { if (bitscount[i] == 1) k = i; if (bitscount[i] == 0) { bitscount[i] = bitscount[k] + bitscount[i - k]; } } // Store the frequency // of respective counts // of set bits Dictionary<int, int> setbits = new Dictionary<int, int>(); for(int j = 0; j < N; j++) { if (setbits.ContainsKey(bitscount[arr[j]])) { setbits[bitscount[arr[j]]]++; } else { setbits[bitscount[arr[j]]] = 1; } } int ans = 0; foreach(KeyValuePair<int, int> it in setbits) { ans += it.Value * (it.Value - 1) / 2; } return ans; } // Driver Code public static void Main(string[] args) { int N = 12; int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; Console.Write(countPairs(arr, N)); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript Program to count // possible number of pairs // of elements with same // number of set bits. // Function to return the // count of Pairs function countPairs(arr, N) { // Get the maximum element var maxm = arr.reduce((a,b)=>Math.max(a,b)); var i, k; // Array to store count of bits // of all elements upto maxm var bitscount = Array(maxm+1).fill(0); // Store the set bits // for powers of 2 for (i = 1; i <= maxm; i *= 2) bitscount[i] = 1; // Compute the set bits for // the remaining elements for (i = 1; i <= maxm; i++) { if (bitscount[i] == 1) k = i; if (bitscount[i] == 0) { bitscount[i] = bitscount[k] + bitscount[i - k]; } } // Store the frequency // of respective counts // of set bits var setbits = new Map(); for (var i = 0; i < N; i++) { if(setbits.has(bitscount[arr[i]])) setbits.set(bitscount[arr[i]], setbits.get(bitscount[arr[i]])+1) else setbits.set(bitscount[arr[i]], 1) } var ans = 0; setbits.forEach((value, key) => { ans += value * (value - 1) / 2; }); return ans; } var N = 12; var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]; document.write( countPairs(arr, N)); </script>
22
Publicación traducida automáticamente
Artículo escrito por noob_coder123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA