Watch the video solution for Bitwise OR of All Subsequence Sums, a medium level problem involving Array, Math, Bit Manipulation. This walkthrough by Programming Live with Larry has 458 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1050 <= nums[i] <= 109Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Subset Sum Bitset DP | O(n * S) | O(S) | When the total sum of elements is small and you want to explicitly track all reachable sums |
| Bit Manipulation Carry Insight | O(n) | O(1) | General case and interview settings where array size is large |