Bitwise ORs of Subarrays - Practice Coding Problems

Bitwise ORs of Subarrays - Problem

Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: arr = [0]

› Output: 1

💡 Note: Only one subarray [0], with bitwise OR = 0. So there is 1 distinct value.

Example 2 — Multiple Elements

$ Input: arr = [1,1,2]

› Output: 3

💡 Note: Subarrays: [1]=1, [1]=1, [2]=2, [1,1]=1, [1,2]=3, [1,1,2]=3. Distinct ORs: {1,2,3}.

Example 3 — All Same Elements

$ Input: arr = [1,2,4]

› Output: 6

💡 Note: Subarrays: [1]=1, [2]=2, [4]=4, [1,2]=3, [2,4]=6, [1,2,4]=7. Distinct ORs: {1,2,3,4,6,7}.

Constraints

1 ≤ arr.length ≤ 5 × 10⁴
0 ≤ arr[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of integers

Generate Subarrays

Find all contiguous non-empty subarrays

Count Distinct ORs

Calculate OR for each subarray and count unique values

Key Takeaway

🎯 Key Insight: Bitwise OR can only add bits, so the number of distinct OR values is limited to at most 32 per position

Asked in

G Google 25 f Facebook 18

The key insight is that bitwise OR can only add bits, never remove them, limiting the number of distinct values. The optimized approach uses set propagation to track OR values efficiently. Time: O(n × 32), Space: O(32).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - All Subarrays	O(n²)	O(n)	Generate all possible subarrays and compute their ORs
Optimized with Set Propagation	O(n × k)	O(k)	Track all possible OR values as we process each element

Brute Force - All Subarrays — Algorithm Steps

Iterate through each possible starting index
For each start, extend subarray to all possible ending positions
Calculate OR for each subarray and add to set
Return size of set

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at each index

Begin subarray at every position

Extend subarray

Grow subarray to right, updating OR

Collect unique ORs

Store all distinct OR values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 2000

int solution(int* arr, int n) {
    int distinctOrs[MAX_SIZE * 32];
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        int currentOr = 0;
        for (int j = i; j < n; j++) {
            currentOr |= arr[j];
            
            // Check if this OR value already exists
            int exists = 0;
            for (int k = 0; k < count; k++) {
                if (distinctOrs[k] == currentOr) {
                    exists = 1;
                    break;
                }
            }
            if (!exists) {
                distinctOrs[count++] = currentOr;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[MAX_SIZE];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops to generate all subarrays, each OR operation is O(1)

⚠ Quadratic Growth

Space Complexity

O(n)

Set to store distinct OR values, at most n distinct values possible

⚡ Linearithmic Space

25.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler