Sum of Bitwise OR of each array element of an array with all elements of another array

0 0 9 minutes read

Given two arrays arr1[] of size M and arr2[] of size N, the task is to find the sum of bitwise OR of each element of arr1[] with every element of the array arr2[].

Examples:

Input: arr1[] = {1, 2, 3}, arr2[] = {1, 2, 3}, M = 3, N = 3
Output: 7 8 9
Explanation:
For arr[0]: Sum = arr1[0]|arr2[0] + arr1[0]|arr2[1] + arr1[0]|arr2[2], Sum = 1|1 + 1|2 + 1|3 = 7
For arr[1], Sum = arr1[1]|arr2[0] + arr1[1]|arr2[1] + arr1[1]|arr2[2], Sum= 2|1 + 2|2 + 2|3 = 8
For arr[2], Sum = arr1[2]|arr2[0] + arr1[2]|arr2[1] + arr1[2]|arr2[2], Sum = 3|1 + 3|2 + 3|3 = 9

Input: arr1[] = {2, 4, 8, 16}, arr2[] = {2, 4, 8, 16}, M = 4, N = 4
Output: 36 42 54 78

Naive Approach: The simplest0 approach to solve this problem to traverse the array arr1[] and for each array element in the array arr[], calculate Bitwise OR of each element in the array arr2[].

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is to use Bit Manipulation to solve the above problem.

According to the Bitwise OR property, while performing the operation, the i^th bit will be set bit only when either of both numbers has a set bit at the i^th position, where 0 ≤ i <32.
Therefore, for a number in arr1[], if the i^th bit is not a set bit, then the i^th place will contribute a sum of K * 2ⁱ , where K is the total number in arr2[] having set bit at the i^th position.
Otherwise, if the number has a set bit at the i^th place, then it will contribute a sum of N * 2ⁱ.

Follow the steps below to solve the problem:

Initialize an integer array, say frequency[], to store the count of numbers in arr2[] having set-bit at i^th position ( 0 ≤ i < 32).
Traverse the array arr2[] and represent each array element in its binary form and increment the count in the frequency[] array by one at the positions having set bit in the binary representations.
Traverse the array arr1[].
1. Initialize an integer variable, say bitwise_OR_sum with 0.
2. Traverse in the range [0, 31] using variable j.
3. If the j^th bit is set in the binary representation of arr2[i], then increment bitwise_OR_sum by N * 2^j. Otherwise, increment by frequency[j] * 2^j
4. Print the sum obtained bitwise_OR_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 sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
void Bitwise_OR_sum_i(int arr1[], int arr2[],
                      int M, int N)
{
 
    // Declaring an array of
    // size 32 to store the
    // count of each bit
    int frequency[32] = { 0 };
 
    // Traverse the array arr1[]
    for (int i = 0; i < N; i++) {
 
        // Current bit position
        int bit_position = 0;
        int num = arr1[i];
 
        // While num exceeds 0
        while (num) {
 
            // Checks if i-th bit
            // is set or not
            if (num & 1) {
 
                // Increment the count at
                // bit_position by one
                frequency[bit_position] += 1;
            }
 
            // Increment bit_position
            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_OR_sum = 0;
 
        // Traverse in the range [0, 31]
        for (int bit_position = 0;
             bit_position < 32;
             bit_position++) {
 
            // Check if current bit is set
            if (num & 1) {
 
                // Increment the Bitwise
                // sum by N*(2^i)
                bitwise_OR_sum
                    += N * value_at_that_bit;
            }
            else {
                bitwise_OR_sum
                    += frequency[bit_position]
                       * value_at_that_bit;
            }
 
            // Right shift num by one
            num >>= 1;
 
            // Left shift valee_at_that_bit by one
            value_at_that_bit <<= 1;
        }
 
        // Print the sum obtained for ith
        // number in arr1[]
        cout << bitwise_OR_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_OR_sum_i(arr1, arr2, M, N);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
  
class GFG{
      
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
static void Bitwise_OR_sum_i(int arr1[], int arr2[],
                             int M, int N)
{
     
    // Declaring an array of
    // size 32 to store the
    // count of each bit
    int frequency[] = new int[32];
    Arrays.fill(frequency, 0);
  
    // Traverse the array arr1[]
    for(int i = 0; i < N; i++)
    {
         
        // Current bit position
        int bit_position = 0;
        int num = arr1[i];
  
        // While num exceeds 0
        while (num != 0) 
        {
             
            // Checks if i-th bit
            // is set or not
            if ((num & 1) != 0)
            {
                 
                // Increment the count at
                // bit_position by one
                frequency[bit_position] += 1;
            }
  
            // Increment bit_position
            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_OR_sum = 0;
  
        // Traverse in the range [0, 31]
        for(int bit_position = 0;
                bit_position < 32;
                bit_position++) 
        {
  
            // Check if current bit is set
            if ((num & 1) != 0) 
            {
                 
                // Increment the Bitwise
                // sum by N*(2^i)
                bitwise_OR_sum += N * value_at_that_bit;
            }
            else
            {
                bitwise_OR_sum += frequency[bit_position] * 
                                  value_at_that_bit;
            }
  
            // Right shift num by one
            num >>= 1;
  
            // Left shift valee_at_that_bit by one
            value_at_that_bit <<= 1;
        }
  
        // Print the sum obtained for ith
        // number in arr1[]
        System.out.print(bitwise_OR_sum + " ");
    }
    return;
}
  
// 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_OR_sum_i(arr1, arr2, M, N);
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
  
# Function to compute sum of Bitwise OR
# of each element in arr1[] with all
# elements of the array arr2[]
def Bitwise_OR_sum_i(arr1, arr2, M, N): 
  
    # Declaring an array of
    # size 32 to store the
    # count of each bit
    frequency = [0] * 32
  
    # Traverse the array arr1[]
    for i in range(N):
  
        # Current bit position
        bit_position = 0
        num = arr1[i]
  
        # While num exceeds 0
        while (num):
  
            # Checks if i-th bit
            # is set or not
            if (num & 1 != 0):
  
                # Increment the count at
                # bit_position by one
                frequency[bit_position] += 1
             
            # Increment bit_position
            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_OR_sum = 0
  
        # Traverse in the range [0, 31]
        for bit_position in range(32):
  
            # Check if current bit is set
            if (num & 1 != 0):
  
                # Increment the Bitwise
                # sum by N*(2^i)
                bitwise_OR_sum += N * value_at_that_bit
             
            else:
                bitwise_OR_sum += (frequency[bit_position] *
                                   value_at_that_bit)
             
            # Right shift num by one
            num >>= 1
  
            # Left shift valee_at_that_bit by one
            value_at_that_bit <<= 1
         
        # Print the sum obtained for ith
        # number in arr1[]
        print(bitwise_OR_sum, end = " ")
     
    return
 
# Driver Code
 
# 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_OR_sum_i(arr1, arr2, M, N)
 
# This code is contributed by code_hunt

C#

// C# program for the above approach 
using System;
class GFG
{
      
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
static void Bitwise_OR_sum_i(int[] arr1, int[] arr2,
                             int M, int N)
{
      
    // Declaring an array of
    // size 32 to store the
    // count of each bit
    int[] frequency = new int[32];
    for(int i = 0; i < 32; i++)
    {
        frequency[i] = 0;
    }
 
    // Traverse the array arr1[]
    for(int i = 0; i < N; i++)
    {
          
        // Current bit position
        int bit_position = 0;
        int num = arr1[i];
   
        // While num exceeds 0
        while (num != 0) 
        {
              
            // Checks if i-th bit
            // is set or not
            if ((num & 1) != 0)
            {
                  
                // Increment the count at
                // bit_position by one
                frequency[bit_position] += 1;
            }
   
            // Increment bit_position
            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_OR_sum = 0;
   
        // Traverse in the range [0, 31]
        for(int bit_position = 0;
                bit_position < 32;
                bit_position++) 
        {
   
            // Check if current bit is set
            if ((num & 1) != 0) 
            {
                  
                // Increment the Bitwise
                // sum by N*(2^i)
                bitwise_OR_sum += N * value_at_that_bit;
            }
            else
            {
                bitwise_OR_sum += frequency[bit_position] * 
                                  value_at_that_bit;
            }
   
            // Right shift num by one
            num >>= 1;
   
            // Left shift valee_at_that_bit by one
            value_at_that_bit <<= 1;
        }
   
        // Print the sum obtained for ith
        // number in arr1[]
        Console.Write(bitwise_OR_sum + " ");
    }
    return;
}
  
// Driver Code
public static 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_OR_sum_i(arr1, arr2, M, N);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
// Javascript program for the above approach
 
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
function Bitwise_OR_sum_i(arr1, arr2, M, N) {
 
    // Declaring an array of
    // size 32 to store the
    // count of each bit
    let frequency = new Array(32).fill(0);
 
    // Traverse the array arr1[]
    for (let i = 0; i < N; i++) {
 
        // Current bit position
        let bit_position = 0;
        let num = arr1[i];
 
        // While num exceeds 0
        while (num) {
 
            // Checks if i-th bit
            // is set or not
            if (num & 1) {
 
                // Increment the count at
                // bit_position by one
                frequency[bit_position] += 1;
            }
 
            // Increment bit_position
            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_OR_sum = 0;
 
        // Traverse in the range [0, 31]
        for (let bit_position = 0; bit_position < 32; bit_position++) {
 
            // Check if current bit is set
            if (num & 1) {
 
                // Increment the Bitwise
                // sum by N*(2^i)
                bitwise_OR_sum += N * value_at_that_bit;
            }
            else {
                bitwise_OR_sum += frequency[bit_position] * value_at_that_bit;
            }
 
            // Right shift num by one
            num >>= 1;
 
            // Left shift valee_at_that_bit by one
            value_at_that_bit <<= 1;
        }
 
        // Print the sum obtained for ith
        // number in arr1[]
        document.write(bitwise_OR_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_OR_sum_i(arr1, arr2, M, N);
 
 
// This code is contributed by _saurabh_jaiswal
</script>

Output:

7 8 9

Time Complexity: O(N*32)
Auxiliary Space: O(1) because size of frequency array is constant

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!