Is Bitwise OR of All Subsequence Sums easy or hard?

The problem is rated Medium because the brute-force interpretation suggests subset DP, which is expensive. The challenge is spotting the binary carry insight that collapses the solution to O(n). Once the observation is known, the implementation itself is very short.

Bitwise OR of All Subsequence Sums Python/Java solution

Implement the algorithm by iterating through nums, accumulating the total sum and computing the OR of all elements. Finally return orValue | totalSum. The same logic works in Python, Java, C++, and Go because it only relies on standard integer bitwise operations.

How to solve Bitwise OR of All Subsequence Sums in O(n)?

Iterate through the array and maintain two values: the running sum of all elements and the bitwise OR of the elements. After processing the array, return (orValue | totalSum). The OR captures bits directly present in elements, while the sum introduces higher bits created through carry operations when elements are added in subsequences.

What is the best approach for Bitwise OR of All Subsequence Sums?

The optimal approach uses a bit manipulation observation: compute the bitwise OR of all array elements and also compute the total sum of the array. The final answer is OR(nums) | sum(nums). This works because subset additions can generate binary carries that activate any bit present in the total sum. The algorithm runs in O(n) time and O(1) space.

Is Bitwise OR of All Subsequence Sums asked at Google/Amazon/Meta?

Problems involving bit manipulation and subset reasoning frequently appear in interviews at companies like Google, Amazon, and Meta. This specific problem tests understanding of binary carry propagation and the ability to reduce exponential subset reasoning into a linear-time mathematical insight.

What data structure is used in Bitwise OR of All Subsequence Sums?

The optimal solution does not require complex data structures. It uses simple integer variables with bitwise OR operations and arithmetic addition. Alternative exploratory solutions may use a bitset or dynamic programming array to track reachable subset sums.

What is the time complexity of Bitwise OR of All Subsequence Sums?

The optimal solution runs in O(n) time because the array is scanned once to compute the cumulative sum and the OR of all elements. Space complexity is O(1) since only a few integer variables are maintained. A brute-force subset enumeration would take O(2^n) time, which is infeasible for typical constraints.

Description Hints 3 Solution Video 10:10

2505. Bitwise OR of All Subsequence Sums

Medium63.4% acceptance1 companyPremium elsewhere, free here

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 <= 10⁵
0 <= nums[i] <= 10⁹

Asked at 1 company

Zomato

Topics

Hints open one at a time

Hint 1

Think of each bit separately, i.e. try to figure out if i^th bit is set in the answer.

Hint 2

i^th bit is set in the answer if it's set in one of the array elements or it can be made using some of them.

Hint 3

Try to sum up lower bits and make higher bits.

10:10

Still stuck?Read the written solution, or watch a walkthrough.

Open solution