Sum of Bitwise AND of each array element with the elements of another array
Given two arrays arr1[] of size M and arr2[] of size N, the task is to find the sum of bitwise AND of each element of arr1[] with the elements of the array arr2[].
Examples:
Input: arr1[] = {1, 2, 3}, arr2[] = {1, 2, 3}, M = 3, N = 3
Output: 2 4 6
Explanation:
For elements at index 0 in arr1[], Sum = arr1[0] & arr2[0] + arr1[0] & arr2[1] + arr1[0] & arr2[2], Sum = 1 & 1 + 1 & 2 + 1 & 3 = 2
For elements at index 1 in arr1[], Sum = arr1[1] & arr2[0] + arr1[1] & arr2[1] + arr1[1] & arr2[2], Sum= 2 & 1 + 2 & 2 + 2 & 3 = 4
For elements at index 2 in arr1[], Sum = arr1[2] & arr2[0] + arr1[2] & arr2[1] + arr1[2] & arr2[2], Sum= 3 & 1 + 3 & 2 + 3 & 3 = 6Input: arr1[] = {2, 4, 8, 16}, arr2[] = {2, 4, 8, 16}, M = 4, N = 4
Output: 2 4 8 16
Naive Approach: The simplest approach to solve the problem is to traverse the array arr1[] and for each element of the array arr1[], traverse the array arr2[] and calculate the sum of Bitwise AND of the current elements of arr1[] with all elements of arr2[] for each element
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to use bit manipulation to solve the above problem. Suppose every element of the array can be represented using 32 bits only.
- According to the bitwise AND property, while performing the operation, the ith bit will be set bit only when both numbers have a set bit at the ith position, where 0?i<32.
- Therefore, for a number in arr1[], If the ith bit is a set bit, then the ith place will contribute a sum of K*2i, where K is the total number of numbers in arr2[] having set the bit at the ith position.
Follow the steps below to solve the problem:
- Initialize an integer array frequency[] to store the count of numbers in arr2[] having set the bit at ith position where 0?i<32
- Traverse in the array arr2[] and for each element represent it in binary form and increment the count in the frequency[] array by one at the position having 1 in the binary representation.
- Traverse the array arr1[]
- Initialize an integer variable bitwise_AND_sum with 0.
- Traverse in the range [0, 31] using a variable j.
- If the jth bit is set to bit in the binary representation of arr2[i] then increment bitwise_AND_sum by frequency[j]*2j.
- Print the sum obtained i.e., bitwise_AND_sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to compute the AND sum // for each element of an array void Bitwise_AND_sum_i( int arr1[], int arr2[], int M, int N) { // Declaring an array of // size 32 for storing the // count of each bit int frequency[32] = { 0 }; // Traverse the array arr2[] // and store the count of a // bit in frequency array for ( int i = 0; i < N; i++) { // Current bit position int bit_position = 0; int num = arr1[i]; // While num is greater // than 0 while (num) { // Checks if ith bit is // set or not if (num & 1) { // Increment the count of // bit by one frequency[bit_position] += 1; } // Increment the bit position // by one bit_position += 1; // Right shift the num by one num >>= 1; } } // Traverse in the arr2[] for ( int i = 0; i < M; i++) { int num = arr2[i]; // Store the ith bit // value int value_at_that_bit = 1; // Total required sum int bitwise_AND_sum = 0; // Traverse in the range [0, 31] for ( int bit_position = 0; bit_position < 32; bit_position++) { // Checks if current bit is set if (num & 1) { // Increment the bitwise sum // by frequency[bit_position] // * value_at_that_bit; bitwise_AND_sum += frequency[bit_position] * value_at_that_bit; } // Right shift num by one num >>= 1; // Left shift vale_at_that_bit by one value_at_that_bit <<= 1; } // Print the sum obtained for ith // number in arr1[] cout << bitwise_AND_sum << ' ' ; } return ; } // Driver Code int main() { // Given arr1[] int arr1[] = { 1, 2, 3 }; // Given arr2[] int arr2[] = { 1, 2, 3 }; // Size of arr1[] int N = sizeof (arr1) / sizeof (arr1[0]); // Size of arr2[] int M = sizeof (arr2) / sizeof (arr2[0]); // Function Call Bitwise_AND_sum_i(arr1, arr2, M, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Driver Code public static void main(String[] args) { // Given arr1[] int [] arr1 = { 1 , 2 , 3 }; // Given arr2[] int [] arr2 = { 1 , 2 , 3 }; // Size of arr1[] int N = arr1.length; // Size of arr2[] int M = arr2.length; // Function Call Bitwise_AND_sum_i(arr1, arr2, M, N); } // Function to compute the AND sum // for each element of an array static void Bitwise_AND_sum_i( int arr1[], int arr2[], int M, int N) { // Declaring an array of // size 32 for storing the // count of each bit int [] frequency = new int [ 32 ]; // Traverse the array arr2[] // and store the count of a // bit in frequency array for ( int i = 0 ; i < N; i++) { // Current bit position int bit_position = 0 ; int num = arr1[i]; // While num is greater // than 0 while (num != 0 ) { // Checks if ith bit is // set or not if ((num & 1 ) != 0 ) { // Increment the count of // bit by one frequency[bit_position] += 1 ; } // Increment the bit position // by one bit_position += 1 ; // Right shift the num by one num >>= 1 ; } } // Traverse in the arr2[] for ( int i = 0 ; i < M; i++) { int num = arr2[i]; // Store the ith bit // value int value_at_that_bit = 1 ; // Total required sum int bitwise_AND_sum = 0 ; // Traverse in the range [0, 31] for ( int bit_position = 0 ; bit_position < 32 ; bit_position++) { // Checks if current bit is set if ((num & 1 ) != 0 ) { // Increment the bitwise sum // by frequency[bit_position] // * value_at_that_bit; bitwise_AND_sum += frequency[bit_position] * value_at_that_bit; } // Right shift num by one num >>= 1 ; // Left shift vale_at_that_bit by one value_at_that_bit <<= 1 ; } // Print the sum obtained for ith // number in arr1[] System.out.print( bitwise_AND_sum + " " ); } } } // This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approach # Function to compute the AND sum # for each element of an array def Bitwise_AND_sum_i(arr1, arr2, M, N): # Declaring an array of # size 32 for storing the # count of each bit frequency = [ 0 ] * 32 # Traverse the array arr2[] # and store the count of a # bit in frequency array for i in range (N): # Current bit position bit_position = 0 num = arr1[i] # While num is greater # than 0 while (num): # Checks if ith bit is # set or not if (num & 1 ): # Increment the count of # bit by one frequency[bit_position] + = 1 # Increment the bit position # by one bit_position + = 1 # Right shift the num by one num >> = 1 # Traverse in the arr2[] for i in range (M): num = arr2[i] # Store the ith bit # value value_at_that_bit = 1 # Total required sum bitwise_AND_sum = 0 # Traverse in the range [0, 31] for bit_position in range ( 32 ): # Checks if current bit is set if (num & 1 ): # Increment the bitwise sum # by frequency[bit_position] # * value_at_that_bit bitwise_AND_sum + = frequency[bit_position] * value_at_that_bit # Right shift num by one num >> = 1 # Left shift vale_at_that_bit by one value_at_that_bit << = 1 # Print sum obtained for ith # number in arr1[] print (bitwise_AND_sum, end = " " ) return # Driver Code if __name__ = = '__main__' : # Given arr1[] arr1 = [ 1 , 2 , 3 ] # Given arr2 arr2 = [ 1 , 2 , 3 ] # Size of arr1[] N = len (arr1) # Size of arr2[] M = len (arr2) # Function Call Bitwise_AND_sum_i(arr1, arr2, M, N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG { // Driver code static public void Main() { // Given arr1[] int [] arr1 = { 1, 2, 3 }; // Given arr2[] int [] arr2 = { 1, 2, 3 }; // Size of arr1[] int N = arr1.Length; // Size of arr2[] int M = arr2.Length; // Function Call Bitwise_AND_sum_i(arr1, arr2, M, N); } // Function to compute the AND sum // for each element of an array static void Bitwise_AND_sum_i( int [] arr1, int [] arr2, int M, int N) { // Declaring an array of // size 32 for storing the // count of each bit int [] frequency = new int [32]; // Traverse the array arr2[] // and store the count of a // bit in frequency array for ( int i = 0; i < N; i++) { // Current bit position int bit_position = 0; int num = arr1[i]; // While num is greater // than 0 while (num != 0) { // Checks if ith bit is // set or not if ((num & 1) != 0) { // Increment the count of // bit by one frequency[bit_position] += 1; } // Increment the bit position // by one bit_position += 1; // Right shift the num by one num >>= 1; } } // Traverse in the arr2[] for ( int i = 0; i < M; i++) { int num = arr2[i]; // Store the ith bit // value int value_at_that_bit = 1; // Total required sum int bitwise_AND_sum = 0; // Traverse in the range [0, 31] for ( int bit_position = 0; bit_position < 32; bit_position++) { // Checks if current bit is set if ((num & 1) != 0) { // Increment the bitwise sum // by frequency[bit_position] // * value_at_that_bit; bitwise_AND_sum += frequency[bit_position] * value_at_that_bit; } // Right shift num by one num >>= 1; // Left shift vale_at_that_bit by one value_at_that_bit <<= 1; } // Print the sum obtained for ith // number in arr1[] Console.Write(bitwise_AND_sum + " " ); } } } // The code is contributed by Dharanendra L V |
Javascript
<script> // Javascript program for the above approach // Function to compute the AND sum // for each element of an array function Bitwise_AND_sum_i(arr1, arr2, M, N) { // Declaring an array of // size 32 for storing the // count of each bit let frequency = new Array(32).fill(0); // Traverse the array arr2[] // and store the count of a // bit in frequency array for (let i = 0; i < N; i++) { // Current bit position let bit_position = 0; let num = arr1[i]; // While num is greater // than 0 while (num) { // Checks if ith bit is // set or not if (num & 1) { // Increment the count of // bit by one frequency[bit_position] += 1; } // Increment the bit position // by one bit_position += 1; // Right shift the num by one num >>= 1; } } // Traverse in the arr2[] for (let i = 0; i < M; i++) { let num = arr2[i]; // Store the ith bit // value let value_at_that_bit = 1; // Total required sum let bitwise_AND_sum = 0; // Traverse in the range [0, 31] for (let bit_position = 0; bit_position < 32; bit_position++) { // Checks if current bit is set if (num & 1) { // Increment the bitwise sum // by frequency[bit_position] // * value_at_that_bit; bitwise_AND_sum += frequency[bit_position] * value_at_that_bit; } // Right shift num by one num >>= 1; // Left shift vale_at_that_bit by one value_at_that_bit <<= 1; } // Print the sum obtained for ith // number in arr1[] document.write(bitwise_AND_sum + ' ' ); } return ; } // Driver Code // Given arr1[] let arr1 = [1, 2, 3]; // Given arr2[] let arr2 = [1, 2, 3]; // Size of arr1[] let N = arr1.length; // Size of arr2[] let M = arr2.length // Function Call Bitwise_AND_sum_i(arr1, arr2, M, N); // This code is contributed by _saurabh_jaiswal </script> |
2 4 6
Time Complexity: O(N * 32)
Auxiliary Space: O(N * 32)