LeetCode Problem 2505

Difficulty: 🟡 Medium
Topics: Array, Math, Bit Manipulation, Brainteaser, Prefix Sum

Solution

LeetCode 2505 - Bitwise OR of All Subsequence Sums

Problem Understanding

This problem asks us to compute the bitwise OR of every possible subsequence sum of a given array.

A subsequence is formed by choosing any subset of elements while preserving their original order. Since every element can either be included or excluded, an array of length n has 2^n possible subsequences.

For each subsequence, we calculate its sum. Then we take the bitwise OR of all those sums together and return the final value.

For example, if nums = [2,1], the subsequences are:

• [], sum = 0
• [2], sum = 2
• [1], sum = 1
• [2,1], sum = 3

The final result is:

0 | 2 | 1 | 3 = 3

The constraints are extremely important here:

• nums.length can be as large as 10^5
• nums[i] can be as large as 10^9

A brute force solution that enumerates all subsequences would require O(2^n) time, which is completely infeasible.

The key challenge is discovering a mathematical property that allows us to avoid generating subsequences explicitly.

Several edge cases are important:

• Arrays containing only zeros
• Arrays with one element
• Very large values that produce carries during addition
• Situations where bits become set only because of carry propagation

The problem guarantees non-negative integers, which simplifies bit manipulation because we never need to handle sign bits.

Approaches

Brute Force Approach

The most direct solution is to generate every subsequence recursively or iteratively using bitmasks.

For each subsequence:

1. Compute its sum
2. OR the sum into the answer

This approach is correct because it explicitly evaluates every possible subsequence sum.

However, the number of subsequences is 2^n. Even for n = 40, this becomes too large, and the actual constraint is 10^5.

Therefore, brute force is impossible.

Key Insight

The crucial observation is that we do not actually need to know every subsequence sum individually.

Suppose we process numbers from left to right while maintaining a running prefix sum.

Every subsequence sum can be represented as the sum of some subset of elements. When binary addition happens, carry bits can propagate upward.

A bit can appear in the final OR result if it appears in:

• Any array element directly
• Any carry generated during addition

It turns out that the OR of all subsequence sums is equal to the OR of:

• Every prefix sum
• Every original element

A compact way to compute this is:

answer = OR of all prefix sums and all numbers

As we accumulate the running sum, carries naturally appear in the prefix sum representation, which captures every possible bit that can occur in any subsequence sum.

This reduces the problem to a simple linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(1)	Enumerates every subsequence
Optimal	O(n)	O(1)	Uses prefix sums and bitwise OR

Algorithm Walkthrough

1. Initialize three variables:

• prefix_sum = 0
• answer = 0
• Iterate through the array from left to right.

2. For each number num:

• Add it to prefix_sum
• OR both num and prefix_sum into answer

3. Continue until all elements are processed.
4. Return answer.

The reason this works is that every carry generated during binary addition appears in some prefix sum. Since subsequence sums are formed through combinations of additions, every bit that could ever appear in a subsequence sum eventually appears in either:

• An original number
• A carry propagated into a prefix sum

By OR-ing all prefix sums together, we capture all reachable bits.

Why it works

Binary addition propagates information upward through carry bits. Any bit that can appear in any subsequence sum must originate from either an original set bit or a carry generated while adding numbers together.

The running prefix sums expose all such carry propagation behavior. Therefore, OR-ing every prefix sum together guarantees that every achievable bit appears in the final answer.

Python Solution

from typing import List

class Solution:
    def subsequenceSumOr(self, nums: List[int]) -> int:
        prefix_sum = 0
        answer = 0

        for num in nums:
            prefix_sum += num
            answer |= num
            answer |= prefix_sum

        return answer

The implementation is intentionally compact because the mathematical observation removes the need for dynamic programming or subset generation.

prefix_sum stores the cumulative sum as we iterate through the array.

For each number:

• answer |= num ensures all original bits are included
• answer |= prefix_sum captures all carry-generated bits that emerge during addition

Since Python integers automatically expand to arbitrary precision, we do not need to worry about overflow.

The algorithm performs exactly one pass through the array.

Go Solution

func subsequenceSumOr(nums []int) int64 {
    var prefixSum int64 = 0
    var answer int64 = 0

    for _, num := range nums {
        prefixSum += int64(num)
        answer |= int64(num)
        answer |= prefixSum
    }

    return answer
}

The Go implementation is almost identical to the Python version.

The main difference is that Go requires explicit integer sizing. Since prefix sums can exceed int32, the implementation uses int64.

Each integer from the input slice is converted to int64 before arithmetic and bitwise operations.

Go slices naturally handle empty-like behavior, although the constraints guarantee at least one element.

Worked Examples

Example 1

nums = [2,1,0,3]

We track prefix_sum and answer at each step.

Step	num	prefix_sum	answer calculation	answer
Start	-	0	0	0
1	2	2	0 | 2 | 2	2
2	1	3	2 | 1 | 3	3
3	0	3	3 | 0 | 3	3
4	3	6	3 | 3 | 6	7

Final answer:

7

All subsequence sums are:

0,1,2,3,4,5,6

Their OR equals 7.

Example 2

nums = [0,0,0]

Step	num	prefix_sum	answer
Start	-	0	0
1	0	0	0
2	0	0	0
3	0	0	0

Final answer:

0

No bit is ever set.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Uses only a few variables

The algorithm processes each number exactly once.

No auxiliary data structures proportional to input size are required. The memory usage remains constant regardless of array length.

Test Cases

from typing import List

class Solution:
    def subsequenceSumOr(self, nums: List[int]) -> int:
        prefix_sum = 0
        answer = 0

        for num in nums:
            prefix_sum += num
            answer |= num
            answer |= prefix_sum

        return answer

sol = Solution()

assert sol.subsequenceSumOr([2, 1, 0, 3]) == 7  # Provided example
assert sol.subsequenceSumOr([0, 0, 0]) == 0  # All zeros
assert sol.subsequenceSumOr([5]) == 5  # Single element
assert sol.subsequenceSumOr([1, 2, 4]) == 7  # Independent bits
assert sol.subsequenceSumOr([1, 1, 1]) == 3  # Carry generation
assert sol.subsequenceSumOr([8, 8]) == 24  # Carry into higher bit
assert sol.subsequenceSumOr([1024, 2048]) == 3072  # Large powers of two
assert sol.subsequenceSumOr([3, 5, 6]) == 15  # Multiple carry interactions
assert sol.subsequenceSumOr([0]) == 0  # Minimum valid input
assert sol.subsequenceSumOr([10**9, 10**9]) > 0  # Very large values

Test Summary

Test	Why
[2,1,0,3]	Validates provided example
[0,0,0]	Ensures all-zero handling
[5]	Tests single-element array
[1,2,4]	Verifies independent bit accumulation
[1,1,1]	Tests carry propagation
[8,8]	Validates higher-bit carry creation
[1024,2048]	Tests large bit positions
[3,5,6]	Exercises overlapping carries
[0]	Minimum boundary input
[10**9,10**9]	Stress test for large integers

Edge Cases

All Elements Are Zero

If every number is zero, then every subsequence sum is also zero. A careless implementation might accidentally introduce bits through incorrect initialization or arithmetic.

This implementation handles the case naturally because both prefix_sum and answer remain zero throughout the scan.

Carry Propagation Creates New Bits

An important subtlety is that some bits appear only because of addition carries.

For example:

[8,8]

The number 16 never appears directly in the input, but it appears in the subsequence sum 8 + 8.

The prefix sum becomes 16, so the implementation correctly captures that new bit through:

answer |= prefix_sum

Very Large Numbers

The constraints allow numbers up to 10^9, and cumulative sums can become much larger.

In Python, integers automatically scale to arbitrary precision, so overflow is not an issue.

In Go, the implementation explicitly uses int64 to ensure the running sum safely fits within the integer range.