Problem Description

Given an integer array nums, you need to find the bitwise OR of the sums of all possible subsequences of the array.

A subsequence is a sequence that can be derived from the original array by removing zero or more elements while maintaining the relative order of the remaining elements. For example, if nums = [1, 2, 3], the possible subsequences are: [], [1], [2], [3], [1,2], [1,3], [2,3], and [1,2,3].

For each subsequence, calculate its sum, then take the bitwise OR of all these sums to get the final result.

How the solution works:

The key insight is that we don't need to generate all subsequences explicitly. Instead, we can track how each bit position contributes to the final OR result.

The solution uses an array cnt of size 64 to count how many times each bit position can be set to 1 across all possible subsequence sums.

For each number in nums, we check which bit positions are set to 1 (using (v >> i) & 1) and increment the corresponding counter in cnt[i].

Then, we process the counts from the lowest bit to the highest:

• If cnt[i] > 0, it means at least one subsequence sum has bit i set to 1, so we include 1 << i in our answer using OR operation
• We handle carry-over by adding cnt[i] // 2 to cnt[i + 1], since every two occurrences of a bit at position i create one occurrence at position i + 1 when summing

This approach efficiently computes the bitwise OR of all subsequence sums without explicitly generating all 2^n subsequences.

Intuition

The brute force approach would be to generate all 2^n subsequences, calculate their sums, and then OR all these sums together. However, this would be exponentially slow.

The key observation is that for bitwise OR operations, we only care about whether a particular bit position is ever set to 1 in any of the subsequence sums. Once a bit is set to 1 in the OR result, it stays 1 regardless of how many more times we encounter it.

Let's think about how bits contribute to subsequence sums:

• If a number has bit i set to 1, it contributes 2^i to any subsequence sum that includes it
• Multiple numbers with the same bit set will contribute multiple times 2^i to different subsequence sums
• When we add values like 2^i + 2^i = 2^(i+1), carries can propagate to higher bit positions

For example, if we have two numbers with bit 0 set (contributing value 1 each), they can appear together in some subsequences creating sums with bit 1 set (since 1 + 1 = 2 = 2^1).

This leads us to the counting approach:

1. First, count how many numbers have each bit position set - this tells us the potential contributions at each bit level
2. For each bit position, if at least one number contributes to it (directly or through carry), that bit will appear in some subsequence sum, so we include it in our OR result
3. Handle carry propagation: if we have k contributions at bit position i, they can combine in various ways across different subsequences. The key insight is that k contributions at position i can create k // 2 carries to position i+1

By processing bits from low to high and propagating carries, we capture all possible bit positions that can appear in any subsequence sum, giving us the final OR result without explicitly computing all subsequences.

Learn more about Math and Prefix Sum patterns.

Solution Approach

The solution uses bit manipulation to efficiently compute the result without generating all subsequences.

Data Structure:

• An array cnt of size 64 to track the count of contributions at each bit position (64 bits is sufficient for handling carries from 32-bit integers)

Algorithm Steps:

1. Count bit contributions from original numbers:

   for v in nums:
       for i in range(31):
           if (v >> i) & 1:
               cnt[i] += 1

   • For each number v in the array, check each of its 31 bit positions (0 to 30)
   • Use right shift v >> i and bitwise AND with 1 to check if bit i is set
   • If bit i is set, increment cnt[i] to record this contribution

2. Process counts and handle carries:

   for i in range(63):
       if cnt[i]:
           ans |= 1 << i
       cnt[i + 1] += cnt[i] // 2

   • Iterate through bit positions from 0 to 62
   • If cnt[i] > 0, it means at least one subsequence sum will have bit i set, so we OR 1 << i into our answer
   • Handle carry propagation: cnt[i] // 2 represents how many carries go to the next bit position
     • This works because when summing binary numbers, every two 1s at position i create one 1 at position i+1
     • For example, if 3 subsequences have bit 2 set, when summed in certain combinations, they create 3 // 2 = 1 carry to bit 3

3. Return the result:

   • The variable ans accumulates all bit positions that appear in at least one subsequence sum
   • The final ans is the bitwise OR of all possible subsequence sums

Why this works:

• Each number can be selected or not selected in a subsequence, creating 2^n total subsequences
• The cnt array captures how bits from different numbers can combine across all these subsequences
• The carry propagation ensures we account for sums where multiple numbers with the same bit set create carries to higher positions
• Since OR only cares about whether a bit is ever 1, we just need to know if each bit position is reachable, which this counting approach determines efficiently

Example Walkthrough

Let's walk through the solution with nums = [1, 3].

Step 1: Identify all subsequences and their sums

• Subsequences: [], [1], [3], [1,3]
• Sums: 0, 1, 3, 4
• Expected result: 0 | 1 | 3 | 4 = 7

Step 2: Count bit contributions

Initialize cnt = [0] * 64

For v = 1 (binary: 001):

• Bit 0 is set: cnt[0] += 1 → cnt = [1, 0, 0, ...]

For v = 3 (binary: 011):

• Bit 0 is set: cnt[0] += 1 → cnt = [2, 0, 0, ...]
• Bit 1 is set: cnt[1] += 1 → cnt = [2, 1, 0, ...]

Step 3: Process counts and handle carries

Initialize ans = 0

• i = 0:

  • cnt[0] = 2 > 0, so ans |= 1 << 0 = 1 → ans = 1
  • Carry: cnt[1] += 2 // 2 = 1 → cnt = [2, 2, 0, ...]

• i = 1:

  • cnt[1] = 2 > 0, so ans |= 1 << 1 = 2 → ans = 3
  • Carry: cnt[2] += 2 // 2 = 1 → cnt = [2, 2, 1, 0, ...]

• i = 2:

  • cnt[2] = 1 > 0, so ans |= 1 << 2 = 4 → ans = 7
  • Carry: cnt[3] += 1 // 2 = 0 → cnt = [2, 2, 1, 0, ...]

• i = 3 and beyond: cnt[i] = 0, so no more contributions

Result: ans = 7

Why the carries work:

• cnt[0] = 2 means two numbers have bit 0 set (both 1 and 3)
• When both appear in subsequence [1,3], we get 1 + 3 = 4 = 100₂
• This creates a carry that eventually sets bit 2 in the sum
• The algorithm captures this through carry propagation: the two contributions at bit 0 create a carry to bit 1, and combined with the existing bit 1 from value 3, we get another carry to bit 2

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M) where n is the length of the array and M is the maximum value in the array.

• The outer loop iterates through all n elements in the nums array.
• For each element v, the inner loop iterates through 31 bit positions (since we're checking up to bit position 30, which covers all 32-bit integers).
• The bit position check corresponds to log M where M is the maximum value, as we need to check all bits up to the highest set bit in the maximum value.
• The second loop iterates through 63 positions with constant time operations, contributing O(63) = O(1).
• Overall: O(n × 31) = O(n × log M).

Space Complexity: O(1)

• The cnt array has a fixed size of 64 elements regardless of input size.
• The ans variable uses constant space.
• No additional data structures that scale with input size are used.
• Therefore, the space complexity is O(64) = O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Range Assumptions

A common mistake is assuming that 31 bits (for 32-bit integers) is sufficient for the bit count array. However, when summing multiple numbers, carries can propagate beyond the original bit width.

Pitfall Example:

# WRONG: Only allocating 32 bits
bit_count = [0] * 32  # This can cause index out of bounds

for bit_position in range(31):  # Processing only up to bit 30
    if bit_count[bit_position]:
        result |= 1 << bit_position
    bit_count[bit_position + 1] += bit_count[bit_position] // 2  # Error when bit_position = 30

Solution: Always allocate extra space for carry propagation. Use 64 bits to handle carries from 32-bit integers safely:

bit_count = [0] * 64  # Sufficient space for carries
for bit_position in range(63):  # Process up to bit 62
    # ... rest of the logic

2. Misunderstanding Carry Propagation Logic

Some may incorrectly think that if a bit appears k times, it contributes k to the OR result, or forget to propagate carries entirely.

Pitfall Example:

# WRONG: Directly ORing the count value
for bit_position in range(63):
    if bit_count[bit_position]:
        result |= bit_count[bit_position] << bit_position  # Incorrect!
    # Missing carry propagation

Solution: Remember that OR only cares about presence (0 or 1), not the count. The carry propagation simulates how bits combine during addition:

for bit_position in range(63):
    if bit_count[bit_position]:  # Any non-zero count sets this bit
        result |= 1 << bit_position  # Set only the single bit
    bit_count[bit_position + 1] += bit_count[bit_position] // 2  # Propagate carries

3. Off-by-One Errors in Loop Boundaries

Confusion about whether to process bits 0-30 or 0-31, and whether to iterate to 62 or 63 in the final loop.

Pitfall Example:

# WRONG: Inconsistent boundaries
for number in nums:
    for bit_position in range(32):  # Should be 31 for 0-indexed positions
        if (number >> bit_position) & 1:
            bit_count[bit_position] += 1

for bit_position in range(64):  # Should be 63 to avoid accessing bit_count[64]
    if bit_count[bit_position]:
        result |= 1 << bit_position
    bit_count[bit_position + 1] += bit_count[bit_position] // 2  # Index error!

Solution: Be consistent with boundaries:

• For 32-bit integers, check bits 0-30 (31 positions total)
• In the carry propagation loop, iterate from 0 to 62 to avoid accessing bit_count[64]

for bit_position in range(31):  # Bits 0-30 for 32-bit integers
    # ...
for bit_position in range(63):  # Process up to 62, access up to bit_count[63]
    # ...