Bitwise OR of Sums of All Subsequences

Problem Given an array of n integers, form the sum of every one of the 2^n subsequences (including the empty subsequence, whose sum is 0), then return the bitwise OR of all those sums.

Input / Output

• Input: arr, an array of n integers.
• Output: a single integer — the bitwise OR of all 2^n subsequence sums.

Constraints

• Explicit enumeration costs 2^n and stops being viable once n passes roughly 20–25, so an approach that avoids materialising every subsequence is expected.
• The empty subsequence contributes 0, which never affects an OR.
• The total S = sum(arr) is always itself achievable, so every bit of S necessarily appears in the answer.

Example

• arr = [1,1] → subsequences {}, {1}, {1}, {1,1} with sums 0, 1, 1, 2 → OR = 0 | 1 | 1 | 2 = 3.
• arr = [2,4] → sums 0, 2, 4, 6 → OR = 6. Note the answer exceeds any single element, since bits combine only through the sums.