Skip to main content
Talentd

Bitwise OR of All Subsequence Sums - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathBit ManipulationBrainteaser6 min readAsked at: Zomato
Practice this problem

Problem Statement

Given an integer array nums, return the value of the bitwise OR of the sum of all possible subsequences in the array.

A subsequence is a sequence that can be derived from another sequence by removing zero or more elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [2,1,0,3]
Output: 7
Explanation: All possible subsequence sums that we can have are: 0, 1, 2, 3, 4, 5, 6.
And we have 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7, so we return 7.

Example 2:

Input: nums = [0,0,0]
Output: 0
Explanation: 0 is the only possible subsequence sum we can have, so we return 0.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

Approach Overview

Problem Overview: Given an integer array nums, consider every possible subsequence and compute its sum. The task is to return the bitwise OR of all those subsequence sums. A brute-force approach would enumerate all subsets, but with up to 2^n subsequences this quickly becomes infeasible. The key is understanding how binary carries behave when subset sums are formed.

Approach 1: Subset Sum Bitset DP (O(n * S) time, O(S) space)

A direct way is to compute every achievable subsequence sum using a subset-sum dynamic programming technique. Maintain a bitset where index i indicates whether sum i is achievable. For each number, shift the bitset left by that value and OR it with the current state. After processing all numbers, iterate over the bitset and OR together all indices that are reachable. This approach explicitly models subset sums and works well when the total sum S is small. However, when S becomes large (for example when values reach 1e5), both memory and runtime become impractical.

Approach 2: Bit Manipulation Insight (O(n) time, O(1) space)

The optimal observation comes from how binary addition works. Any subsequence sum is formed by adding some subset of elements. When numbers are added, lower bits can generate carries into higher bits. Because every element can participate in some subsequence, the maximum possible carry propagation is bounded by the total sum of the array. This means every bit that appears either in an individual element or through carries in the total sum can appear in at least one subsequence sum.

Compute two values while scanning the array: the bitwise OR of all elements and the total array sum. The OR of elements captures bits that appear directly in at least one subsequence. The total sum captures higher bits produced by addition carries when multiple elements are combined. The final answer is simply (bitwise_or_of_nums | total_sum). This works because subset combinations can trigger carries that activate every bit present in the total sum representation.

This technique relies on understanding binary carry propagation, making it a classic Bit Manipulation and Math observation problem. The array itself is processed once, so the solution runs in linear time and constant space.

Recommended for interviews: Start by explaining the subset-sum interpretation to show you understand the problem structure. Then pivot to the carry insight and derive the OR(nums) | sum(nums) formula. Interviewers typically expect this optimized Array + bit manipulation reasoning because it reduces an exponential problem to a single linear scan.

Solution

We first use an array cnt to count the number of 1s in each bit position. Then, from the lowest bit to the highest bit, if the number of 1s in that bit position is greater than 0, we add the value represented by that bit to the answer. Then, we check if there can be a carry-over, and if so, we add it to the next bit.

The time complexity is O(n times log M), where n is the length of the array and M is the maximum value in the array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Subset Sum Bitset DPO(n * S)O(S)When the total sum of elements is small and you want to explicitly track all reachable sums
Bit Manipulation Carry InsightO(n)O(1)General case and interview settings where array size is large

Video Solution

2505. Bitwise OR of All Subsequence Sums - Week 5/5 Leetcode April Challenge • Programming Live with Larry • 471 views views

Frequently Asked Questions

Is Bitwise OR of All Subsequence Sums easy or hard?
The problem is rated Medium because the brute-force interpretation suggests subset DP, which is expensive. The challenge is spotting the binary carry insight that collapses the solution to O(n). Once the observation is known, the implementation itself is very short.
Bitwise OR of All Subsequence Sums Python/Java solution
Implement the algorithm by iterating through nums, accumulating the total sum and computing the OR of all elements. Finally return orValue | totalSum. The same logic works in Python, Java, C++, and Go because it only relies on standard integer bitwise operations.
How to solve Bitwise OR of All Subsequence Sums in O(n)?
Iterate through the array and maintain two values: the running sum of all elements and the bitwise OR of the elements. After processing the array, return (orValue | totalSum). The OR captures bits directly present in elements, while the sum introduces higher bits created through carry operations when elements are added in subsequences.
What is the best approach for Bitwise OR of All Subsequence Sums?
The optimal approach uses a bit manipulation observation: compute the bitwise OR of all array elements and also compute the total sum of the array. The final answer is OR(nums) | sum(nums). This works because subset additions can generate binary carries that activate any bit present in the total sum. The algorithm runs in O(n) time and O(1) space.
Is Bitwise OR of All Subsequence Sums asked at Google/Amazon/Meta?
Problems involving bit manipulation and subset reasoning frequently appear in interviews at companies like Google, Amazon, and Meta. This specific problem tests understanding of binary carry propagation and the ability to reduce exponential subset reasoning into a linear-time mathematical insight.
What data structure is used in Bitwise OR of All Subsequence Sums?
The optimal solution does not require complex data structures. It uses simple integer variables with bitwise OR operations and arithmetic addition. Alternative exploratory solutions may use a bitset or dynamic programming array to track reachable subset sums.
What is the time complexity of Bitwise OR of All Subsequence Sums?
The optimal solution runs in O(n) time because the array is scanned once to compute the cumulative sum and the OR of all elements. Space complexity is O(1) since only a few integer variables are maintained. A brute-force subset enumeration would take O(2^n) time, which is infeasible for typical constraints.

Ready to solve this problem?

Practice Bitwise OR of All Subsequence Sums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bitwise ORs of Subarrays