Bitwise OR of All Subsequence Sums

Bitwise OR of All Subsequence Sums

What is this problem about?

This is a high-level mathematical and bitwise problem. You are given an array of integers, and you need to find the bitwise OR of the sums of all possible non-empty subsequences. Because the number of subsequences is $2^n - 1$, you cannot calculate every sum individually. You need a more efficient strategy based on the properties of binary numbers and bitwise operations.

Why is this asked in interviews?

Zomato and other tech companies ask this to evaluate a candidate's "Brainteaser" and Math skills. It requires looking beyond the brute-force approach and finding a property that simplifies the problem. It tests your ability to think about how bits accumulate and whether you can identify that certain bits in the final result are guaranteed to be 1 based on the input values.

Algorithmic pattern used

This problem relies on a combination of Prefix Sum and Bitwise Analysis. A key observation is that if we can form sums in a certain range, the bitwise OR of those sums often fills in all bits up to the maximum possible sum. Specifically, the problem often reduces to finding which bits can be "set" by combining numbers, and then ORing those bits together.

Example explanation

Array: [1, 2, 4] Subsequences and their sums:

• [1] -> 1
• [2] -> 2
• [4] -> 4
• [1,2] -> 3
• [1,4] -> 5
• [2,4] -> 6
• [1,2,4] -> 7 Bitwise OR of sums: 1 | 2 | 4 | 3 | 5 | 6 | 7 = 7. Notice that the OR of the individual elements (1|2|4 = 7) and the OR of all subsequence sums (7) are the same in this simple case. In more complex cases, the result is usually the bitwise OR of all values in the range from the minimum element to the total sum of the array.

Common mistakes candidates make

The biggest mistake is trying to generate all subsequences (exponential time). Another is failing to realize that the bitwise OR of a continuous range of numbers [min, max] can be calculated very quickly. Many candidates also get stuck trying to use dynamic programming (like the subset sum problem), which is too slow if the values are large.

Interview preparation tip

When you see "bitwise OR of all sums," consider the range of possible sums. If you can form a dense enough set of sums, the bitwise OR will effectively be a string of 1s up to the highest bit of the total sum.