Count subarrays having even Bitwise OR

0 0 6 minutes read

Given an array arr[] consisting of N positive integers, the task is to count the number of subarrays whose Bitwise OR of its elements even.

Examples:

Input: arr[] = {1, 5, 4, 2, 6 }
Output: 6
Explanation:
The subarrays with even Bitwise OR are {4}, {2}, {6}, {2, 6}, {4, 2}, {4, 2, 6}.
Therefore, the number of subarrays having even Bitwise OR are 6.

Input: arr[] ={2, 5, 6, 8}
Output: 4

Naive Approach: The simplest approach to solve the problem is to generate all subarrays and if the Bitwise OR of any subarray is even, then increase the count of such subarrays. After checking for all the subarrays, print the count obtained as the result.

Time Complexity: O(N³)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by observing the fact that if any of the elements in the subarray is odd, then it will surely make the Bitwise OR of the subarray odd. Therefore, the idea is to find the length of the continuous segment in the array which is even, and add its contribution to the total count.
Follow the steps below to solve the problem:

Initialize a variable, say, count, to store the total number of subarrays having Bitwise OR as even.
Initialize a variable, say L, to store the count of adjacent elements that are even.
Traverse the given array arr[] and perform the following steps:
- If the current element is even then, increment the value of L by 1.
- Otherwise, add the value L * (L + 1) / 2 to the variable count and update L to 0.
If the value of L is non-zero, then add L*(L + 1)/2 to the variable count.
After completing the above steps, print the value of count as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// subarrays having even Bitwise OR
int bitOr(int arr[], int N)
{
    // Store number of subarrays
    // having even bitwise OR
    int count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    int length = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If the element is even
        if (arr[i] % 2 == 0) {
 
            // Increment size of the
            // current continuous sequence
// of even array elements
            length++;
        }
 
        // If arr[i] is odd
        else {
 
            // If length is non zero
            if (length != 0) {
 
                // Adding contribution of
                // subarrays consisting
                // only of even numbers
                count += ((length)
                          * (length + 1))
                         / 2;
            }
 
            // Make length of subarray as 0
            length = 0;
        }
    }
 
    // Add contribution of previous subarray
    count += ((length) * (length + 1)) / 2;
 
    // Return total count of subarrays
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 4, 2, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << bitOr(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to count the number of
// subarrays having even Bitwise OR
static int bitOr(int arr[], int N)
{
     
    // Store number of subarrays
    // having even bitwise OR
    int count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    int length = 0;
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // If the element is even
        if (arr[i] % 2 == 0)
        {
             
            // Increment size of the
            // current continuous sequence
            // of even array elements
            length++;
        }
 
        // If arr[i] is odd
        else
        {
             
            // If length is non zero
            if (length != 0)
            {
                 
                // Adding contribution of
                // subarrays consisting
                // only of even numbers
                count += ((length) * (length + 1)) / 2;
            }
 
            // Make length of subarray as 0
            length = 0;
        }
    }
 
    // Add contribution of previous subarray
    count += ((length) * (length + 1)) / 2;
 
    // Return total count of subarrays
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 5, 4, 2, 6 };
    int N = arr.length;
 
    // Function Call
    System.out.print(bitOr(arr, N));
}
}
 
// This code is contributed by splevel62

Python3

# Python3 program for the above approach
 
# Function to count the number of
# subarrays having even Bitwise OR
def bitOr(arr, N):
     
    # Store number of subarrays
    # having even bitwise OR
    count = 0
 
    # Store the length of the current
    # subarray having even numbers
    length = 0
 
    # Traverse the array
    for i in range(N):
 
        # If the element is even
        if (arr[i] % 2 == 0):
 
            # Increment size of the
            # current continuous sequence
            # of even array elements
            length += 1
             
        # If arr[i] is odd
        else:
             
            # If length is non zero
            if (length != 0):
 
                # Adding contribution of
                # subarrays consisting
                # only of even numbers
                count += ((length) * (length + 1)) // 2
 
            # Make length of subarray as 0
            length = 0
 
    # Add contribution of previous subarray
    count += ((length) * (length + 1)) // 2
 
    # Return total count of subarrays
    return count
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 5, 4, 2, 6 ]
    N = len(arr)
 
    # Function Call
    print (bitOr(arr, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG
{
 
  // Function to count the number of
  // subarrays having even Bitwise OR
  static int bitOr(int[] arr, int N)
  {
 
    // Store number of subarrays
    // having even bitwise OR
    int count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    int length = 0;
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
 
      // If the element is even
      if (arr[i] % 2 == 0)
      {
 
        // Increment size of the
        // current continuous sequence
        // of even array elements
        length++;
      }
 
      // If arr[i] is odd
      else
      {
 
        // If length is non zero
        if (length != 0)
        {
 
          // Adding contribution of
          // subarrays consisting
          // only of even numbers
          count += ((length) * (length + 1)) / 2;
        }
 
        // Make length of subarray as 0
        length = 0;
      }
    }
 
    // Add contribution of previous subarray
    count += ((length) * (length + 1)) / 2;
 
    // Return total count of subarrays
    return count;
  }
 
  // Driver code
  static void Main()
  {
    int[] arr = { 1, 5, 4, 2, 6 };
    int N = arr.Length;
 
    // Function Call
    Console.Write(bitOr(arr, N));
  }
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to count the number of
// subarrays having even Bitwise OR
function bitOr(arr, N)
{
    // Store number of subarrays
    // having even bitwise OR
    var count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    var length = 0;
    var i;
 
    // Traverse the array
    for (i = 0; i < N; i++) {
 
        // If the element is even
        if (arr[i] % 2 == 0) {
 
            // Increment size of the
            // current continuous sequence
// of even array elements
            length++;
        }
 
        // If arr[i] is odd
        else {
 
            // If length is non zero
            if (length != 0) {
 
                // Adding contribution of
                // subarrays consisting
                // only of even numbers
                count += Math.floor((length)
                          * (length + 1)
                         / 2);
            }
 
            // Make length of subarray as 0
            length = 0;
        }
    }
 
    // Add contribution of previous subarray
    count += Math.floor((length) * (length + 1) / 2);
 
    // Return total count of subarrays
    return count;
}
 
// Driver Code
 
    var arr = [1, 5, 4, 2, 6]
    var N = arr.length;
 
    // Function Call
    document.write(bitOr(arr, N));
 
</script>

Output:

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

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!