Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la suma de Bitwise AND de todos los tripletes posibles (arr[i], arr[j], arr[k]) tal que i < j < k .
Ejemplos:
Entrada: arr[] = {3, 5, 4, 7}
Salida: 5
Explicación: Suma de Bitwise AND de todos los tripletes posibles = (3 & 5 & 4) + (3 & 5 & 7) + (3 & 4 & 7) + (5 y 4 y 7) = 0 + 1 + 0 + 4 = 5.Entrada: arr[] = {4, 4, 4}
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los tripletes posibles (i, j, k) de la array dada de modo que i < j < k e imprimir la suma de Bitwise AND de todos los tripletes posibles.
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 calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) void tripletAndSum(int arr[], int n) { // Stores the resultant sum of // Bitwise AND of all triplets int ans = 0; // Generate all triplets of // (arr[i], arr[j], arr[k]) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { // Add Bitwise AND to ans ans += arr[i] & arr[j] & arr[k]; } } } // Print the result cout << ans; } // Driver Code int main() { int arr[] = { 3, 5, 4, 7 }; int N = sizeof(arr) / sizeof(arr[0]); tripletAndSum(arr, N); //This code is contributed by Potta Lokesh return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { // Function to calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) public static void tripletAndSum(int arr[], int n) { // Stores the resultant sum of // Bitwise AND of all triplets int ans = 0; // Generate all triplets of // (arr[i], arr[j], arr[k]) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { // Add Bitwise AND to ans ans += arr[i] & arr[j] & arr[k]; } } } // Print the result System.out.println(ans); } public static void main(String[] args) { int arr[] = { 3, 5, 4, 7 }; int N = arr.length; tripletAndSum(arr, N); } } //This code is contributed by Potta Lokesh
Python3
# Python3 program for the above approach # Function to calculate sum of Bitwise # AND of all unordered triplets from # a given array such that (i < j < k) def tripletAndSum(arr, n): # Stores the resultant sum of # Bitwise AND of all triplets ans = 0 # Generate all triplets of # (arr[i], arr[j], arr[k]) for i in range(n): for j in range(i + 1, n, 1): for k in range(j + 1, n, 1): # Add Bitwise AND to ans ans += arr[i] & arr[j] & arr[k] # Print the result print(ans) # Driver Code if __name__ == '__main__': arr = [ 3, 5, 4, 7 ] N = len(arr) tripletAndSum(arr, N) # This code is contributed by bgangwar59
C#
// C# program for the above approach using System; class GFG{ // Function to calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) public static void tripletAndSum(int[] arr, int n) { // Stores the resultant sum of // Bitwise AND of all triplets int ans = 0; // Generate all triplets of // (arr[i], arr[j], arr[k]) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { // Add Bitwise AND to ans ans += arr[i] & arr[j] & arr[k]; } } } // Print the result Console.WriteLine(ans); } // Driver code static public void Main() { int[] arr = { 3, 5, 4, 7 }; int N = arr.Length; tripletAndSum(arr, N); } } // This code is contributed by splevel62.
Javascript
<script> // JavaScript program for the above approach // Function to calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) function tripletAndSum(arr, n) { // Stores the resultant sum of // Bitwise AND of all triplets let ans = 0; // Generate all triplets of // (arr[i], arr[j], arr[k]) for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { for (let k = j + 1; k < n; k++) { // Add Bitwise AND to ans ans += arr[i] & arr[j] & arr[k]; } } } // Print the result document.write(ans); } // Driver Code let arr = [3, 5, 4, 7]; let N = arr.length tripletAndSum(arr, N); // This code is contributed by Potta Lokesh </script>
5
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar teniendo en cuenta la representación binaria de los números. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 que almacene la suma resultante de Bitwise AND de todos los tripletes posibles.
- Iterar un ciclo sobre el rango [0, 31] y realizar los siguientes pasos:
- Inicialice una variable, digamos cnt como 0 que almacena el recuento de elementos de array que tienen el i -ésimo bit como establecido.
- Recorra la array dada y si el bit i ésimo está establecido , incremente el valor de cnt en 1 .
- Después del paso anterior, para todos los tripletes posibles que tienen el i -ésimo bit , se le aporta el valor (( cnt C 3 )*2 i ) a la suma resultante. Por lo tanto, agregue este valor a la variable cnt .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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 calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) int tripletAndSum(int arr[], int n) { // Stores the resultant sum of // Bitwise AND of all triplets int ans = 0; // Traverse over all the bits for (int bit = 0; bit < 32; bit++) { int cnt = 0; // Count number of elements // with the current bit set for (int i = 0; i < n; i++) { if (arr[i] & (1 << bit)) cnt++; } // There are (cnt)C(3) numbers // with the current bit set and // each triplet contributes // 2^bit to the result ans += (1 << bit) * cnt * (cnt - 1) * (cnt - 2) / 6; } // Return the resultant sum return ans; } // Driver Code int main() { int arr[] = { 3, 5, 4, 7 }; int N = sizeof(arr) / sizeof(arr[0]); cout << tripletAndSum(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) static int tripletAndSum(int[] arr, int n) { // Stores the resultant sum of // Bitwise AND of all triplets int ans = 0; // Traverse over all the bits for(int bit = 0; bit < 32; bit++) { int cnt = 0; // Count number of elements // with the current bit set for(int i = 0; i < n; i++) { if ((arr[i] & (1 << bit)) != 0) cnt++; } // There are (cnt)C(3) numbers // with the current bit set and // each triplet contributes // 2^bit to the result ans += (1 << bit) * cnt * (cnt - 1) * (cnt - 2) / 6; } // Return the resultant sum return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 3, 5, 4, 7 }; int N = arr.length; System.out.print(tripletAndSum(arr, N)); } } // This code is contributed by subham348
Python3
# Python program for the above approach # Function to calculate sum of Bitwise # AND of all unordered triplets from # a given array such that (i < j < k) def tripletAndSum(arr, n): # Stores the resultant sum of # Bitwise AND of all triplets ans = 0 # Traverse over all the bits for bit in range(32): cnt = 0 # Count number of elements # with the current bit set for i in range(n): if(arr[i] & (1 << bit)): cnt+=1 # There are (cnt)C(3) numbers # with the current bit set and # each triplet contributes # 2^bit to the result ans += (1 << bit) * cnt * (cnt - 1) * (cnt - 2) // 6 # Return the resultant sum return ans # Driver Code arr = [3, 5, 4, 7] N = len(arr) print(tripletAndSum(arr, N)) # this code is contributed by shivanisinghss2110
C#
// C# program for the above approach using System; class GFG{ // Function to calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) static int tripletAndSum(int[] arr, int n) { // Stores the resultant sum of // Bitwise AND of all triplets int ans = 0; // Traverse over all the bits for(int bit = 0; bit < 32; bit++) { int cnt = 0; // Count number of elements // with the current bit set for(int i = 0; i < n; i++) { if ((arr[i] & (1 << bit)) != 0) cnt++; } // There are (cnt)C(3) numbers // with the current bit set and // each triplet contributes // 2^bit to the result ans += (1 << bit) * cnt * (cnt - 1) * (cnt - 2) / 6; } // Return the resultant sum return ans; } // Driver Code public static void Main() { int[] arr = { 3, 5, 4, 7 }; int N = arr.Length; Console.Write(tripletAndSum(arr, N)); } } // This code is contributed by rishavmahato348
Javascript
<script> // Javascript program for the above approach // Function to calculate sum of Bitwise // AND of all unordered triplets from // a given array such that (i < j < k) function tripletAndSum(arr, n) { // Stores the resultant sum of // Bitwise AND of all triplets let ans = 0; // Traverse over all the bits for (let bit = 0; bit < 32; bit++) { let cnt = 0; // Count number of elements // with the current bit set for (let i = 0; i < n; i++) { if (arr[i] & (1 << bit)) cnt++; } // There are (cnt)C(3) numbers // with the current bit set and // each triplet contributes // 2^bit to the result ans += (1 << bit) * cnt * (cnt - 1) * (cnt - 2) / 6; } // Return the resultant sum return ans; } // Driver Code let arr = [3, 5, 4, 7]; let N = arr.length; document.write(tripletAndSum(arr, N)); // This code is contributed by _saurabh_jaiswal. </script>
5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA