Ctrl K

OR of All Subset Sums

Medium
You are given an array values of non-negative integers. Pick any subset of its elements (empty or the whole array included) and add up the chosen numbers. Do this for every possible subset. Return the bitwise OR (|) of all the sums you get. There are far too many subsets to try them all, so look for a pattern.
Example 1
values=[4, 1, 2] → 7

Picking any subset gives the sums 0, 1, 2, …, 7. Their bitwise OR is 7.

Example 2
values=[8, 8] → 24

The possible sums are 0, 8 and 16. 8 | 16 = 24.

Example 3
values=[0] → 0

Every sum is zero.

Constraints
  • 1 ≤ len(values) ≤ 10⁵
  • 0 ≤ values[i] ≤ 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsTake From Any Pile MediumXOR Tile Duel HardSum of Bit Differences MediumEight Lamps After Many Nights MediumSplit Into Equal-XOR Halves Medium
loading Python…
Input
values=[4, 1, 2]
Expected
7

Run checks the first 3 tests in your browser. Submit checks all 84 tests on the server, hidden ones included.