What is the time complexity of Bitwise ORs of Subarrays?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Bitwise ORs of Subarrays?

This problem uses Array, Dynamic Programming, Bit Manipulation. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Bitwise ORs of Subarrays?

Insight 1: The bitwise OR operation is monotonic, meaning that as you add more elements to a subarray and OR them together, the result can only stay the same or increase (in terms of the numerical value, as more bits can be set to 1). Insight 2: For each element in the array, we only need to keep track of the distinct OR values that can be obtained by ending the subarray at that element. This is because any OR value obtained earlier can be extended to include the current element.

Which companies ask LeetCode 898. Bitwise ORs of Subarrays in interviews?

This problem is frequently asked at tcs.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Bitwise ORs of Subarrays - LeetCode 898 Solution

Bitwise ORs of Subarrays - Complete Solution Guide

Bitwise ORs of Subarrays is LeetCode problem 898, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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. Example 1: Input: arr = [0] Output: 1 Explanation: There is only one possible result: 0. Example 2: Input: arr = [1,1,2] Output: 3 Explanation: The possible subarrays are [1

Detailed Explanation

The problem asks us to find the number of *distinct* bitwise OR results of all possible non-empty subarrays of a given integer array `arr`. A subarray is a contiguous sequence of elements within the array. The bitwise OR of a subarray is calculated by performing the bitwise OR operation on all the elements within that subarray. We need to consider all possible subarrays, calculate their bitwise OR, and then count the number of unique results.

Solution Approach

The provided solutions use a dynamic programming approach by maintaining a set `cur` that represents the distinct bitwise OR values of subarrays ending at the current index. For each element `x` in the array, a new set `nextCur` is created. `nextCur` includes the element `x` itself, and also all the bitwise ORs of `x` with the values present in the `cur` set (i.e., the ORs of the subarrays ending at the previous index). The `cur` set is then updated to `nextCur`, and all elements in `cur` are added to a result set `res`. The size of `res` gives the count of distinct bitwise OR values.

Step-by-Step Algorithm

Step 1: Initialize an empty set `res` to store the distinct bitwise OR values.
Step 2: Initialize an empty set `cur` to store the distinct bitwise OR values of subarrays ending at the current index.
Step 3: Iterate through the input array `arr`.
Step 4: For each element `x` in `arr`:
Step 4.1: Create a new set `nextCur` and add `x` to it.
Step 4.2: Iterate through the `cur` set and add the bitwise OR of `x` and each element `y` in `cur` to `nextCur`.
Step 4.3: Update `cur` to `nextCur`.
Step 4.4: Add all elements in `cur` to `res`.
Step 5: Return the size of `res`.

Key Insights

Insight 1: The bitwise OR operation is monotonic, meaning that as you add more elements to a subarray and OR them together, the result can only stay the same or increase (in terms of the numerical value, as more bits can be set to 1).
Insight 2: For each element in the array, we only need to keep track of the distinct OR values that can be obtained by ending the subarray at that element. This is because any OR value obtained earlier can be extended to include the current element.
Insight 3: The maximum number of distinct bitwise OR values ending at a given index is limited by the number of bits in the input elements (because each new OR operation can only add new bits to the result. In the constraints, the elements are limited to 10^9, which requires 30 bits. Thus the size of the set 'cur' is bounded by 30, but it's simpler to just iterate through all ORs ending at the previous index). While the set can theoretically reach n, in practice it is much smaller.
Insight 4: Using a set allows us to efficiently store and check for distinct values.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Dynamic Programming, Bit Manipulation.

Companies

Asked at: tcs.

Bitwise ORs of Subarrays | LeetCode 898

Medium

Array Dynamic Programming Bit Manipulation

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> cur = new HashSet<>();
        for (int x : arr) {
            Set<Integer> nextCur = new HashSet<>();
            nextCur.add(x);
            for (int y : cur) {
                nextCur.add(y | x);
            }
            cur = nextCur;
            res.addAll(cur);
        }
        return res.size();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 898: Bitwise ORs of Subarrays - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Bit Manipulation

Companies

tcs

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:898

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize an empty set `res` to store the distinct bitwise OR values.
2
Step 2: Initialize an empty set `cur` to store the distinct bitwise OR values of subarrays ending at the current index.
3
Step 3: Iterate through the input array `arr`.
4
Step 4: For each element `x` in `arr`:
5
Step 4.1: Create a new set `nextCur` and add `x` to it.
6
Step 4.2: Iterate through the `cur` set and add the bitwise OR of `x` and each element `y` in `cur` to `nextCur`.
7
Step 4.3: Update `cur` to `nextCur`.
8
Step 4.4: Add all elements in `cur` to `res`.
9
Step 5: Return the size of `res`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The outer loop iterates `n` times (the length of the array). The inner loop (iterating through `cur`) appears to be O(n) in the worst case. The sets `cur` and `res` stores at most n unique values in the worst case (every value in the array is distinct). The set operations (add, contains) take O(1) on average. However, because the values `cur` can only grow when another bit is set (and given the constraint), the size of cur is bounded by 30 (number of bits in the largest value) making the inner loop roughly O(1). Thus the time complexity ends up being O(n). The space complexity is determined by the sets `res` and `cur`, which can contain up to `n` elements each in the worst case, making the space complexity O(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible subarrays, calculate their bitwise OR, and store the distinct results in a set. This approach is straightforward but less efficient.

Time: O(n^2)Space: O(n)

Trade-offs: The brute force is simple to understand but it's inefficient for large inputs, making the dynamic programming approach preferable.

✨

Key Insights

1Insight 1: The bitwise OR operation is monotonic, meaning that as you add more elements to a subarray and OR them together, the result can only stay the same or increase (in terms of the numerical value, as more bits can be set to 1).
2Insight 2: For each element in the array, we only need to keep track of the distinct OR values that can be obtained by ending the subarray at that element. This is because any OR value obtained earlier can be extended to include the current element.
3Insight 3: The maximum number of distinct bitwise OR values ending at a given index is limited by the number of bits in the input elements (because each new OR operation can only add new bits to the result. In the constraints, the elements are limited to 10^9, which requires 30 bits. Thus the size of the set 'cur' is bounded by 30, but it's simpler to just iterate through all ORs ending at the previous index). While the set can theoretically reach n, in practice it is much smaller.
4Insight 4: Using a set allows us to efficiently store and check for distinct values.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Input array with all zeros: The algorithm correctly returns 1.
Edge case 2: Input array with identical elements: The algorithm efficiently handles it, adding only unique values to the result set.
Edge case 3: Input array with a single element: The algorithm correctly returns 1.
Edge case 4: Large input array with values near the maximum limit: The algorithm still works as the size of each `cur` set would depend on the number of distinct bitwise ORs which is at most `n`

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering all possible subarrays leading to an incorrect result.

✗Common mistake 2: Not removing duplicate bitwise OR results. Make sure to use a `Set` and not a `List` in languages like Java, C++, and Python.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression where identifying unique bit patterns can reduce storage space.

🏦Real-world scenario 2: Network analysis where identifying unique bitwise combinations of network packets can assist in traffic analysis.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 26, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Bitwise ORs of Subarrays"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?