Problem

Given an integer array nums, return the value of the bitwiseOR of the sum of all possiblesubsequences 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.

Examples

Example 1:

1
2
3
4

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:

1
2
3

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^5
  • 0 <= nums[i] <= 109

Solution

Method 1 – Prefix Sum and Set

Intuition

We can use a set to keep track of all possible sums of subsequences. For each number, update the set with all new sums that can be formed by adding the number to existing sums. The answer is the bitwise OR of all these sums.

Approach

  1. Initialize a set with 0 (the sum of the empty subsequence).
  2. For each number in the array, for each sum in the set, add (sum + num) to a new set.
  3. Merge the new set into the main set.
  4. Compute the bitwise OR of all sums in the set (excluding 0 if required).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def subsequenceSumOr(self, nums: list[int]) -> int:
        sums = set([0])
        for num in nums:
            new_sums = set()
            for s in sums:
                new_sums.add(s + num)
            sums |= new_sums
        ans = 0
        for s in sums:
            ans |= s
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int subsequenceSumOr(vector<int>& nums) {
        unordered_set<int> sums = {0};
        for (int num : nums) {
            unordered_set<int> new_sums;
            for (int s : sums) new_sums.insert(s + num);
            sums.insert(new_sums.begin(), new_sums.end());
        }
        int ans = 0;
        for (int s : sums) ans |= s;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public int subsequenceSumOr(int[] nums) {
        Set<Integer> sums = new HashSet<>();
        sums.add(0);
        for (int num : nums) {
            Set<Integer> newSums = new HashSet<>();
            for (int s : sums) newSums.add(s + num);
            sums.addAll(newSums);
        }
        int ans = 0;
        for (int s : sums) ans |= s;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun subsequenceSumOr(nums: IntArray): Int {
        val sums = mutableSetOf(0)
        for (num in nums) {
            val newSums = mutableSetOf<Int>()
            for (s in sums) newSums.add(s + num)
            sums.addAll(newSums)
        }
        var ans = 0
        for (s in sums) ans = ans or s
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func subsequenceSumOr(nums []int) int {
    sums := map[int]struct{}{0: {}}
    for _, num := range nums {
        newSums := map[int]struct{}{}
        for s := range sums {
            newSums[s+num] = struct{}{}
        }
        for s := range newSums {
            sums[s] = struct{}{}
        }
    }
    ans := 0
    for s := range sums {
        ans |= s
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::collections::HashSet;
impl Solution {
    pub fn subsequence_sum_or(nums: Vec<i32>) -> i32 {
        let mut sums = HashSet::new();
        sums.insert(0);
        for num in nums {
            let mut new_sums = HashSet::new();
            for &s in &sums {
                new_sums.insert(s + num);
            }
            sums.extend(new_sums);
        }
        let mut ans = 0;
        for s in sums {
            ans |= s;
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(2^n) in the worst case (all subset sums are unique)
  • 🧺 Space complexity: O(2^n)