Question

2505. Bitwise OR of All Subsequence Sums

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def subsequenceSumOr(self, nums: List[int]) -> int:
    cnt = [0] * 64
    ans = 0
    for v in nums:
      for i in range(31):
        if (v >> i) & 1:
          cnt[i] += 1
    for i in range(63):
      if cnt[i]:
        ans |= 1 << i
      cnt[i + 1] += cnt[i] // 2
    return ans

class Solution {
  public long subsequenceSumOr(int[] nums) {
    long[] cnt = new long[64];
    long ans = 0;
    for (int v : nums) {
      for (int i = 0; i < 31; ++i) {
        if (((v >> i) & 1) == 1) {
          ++cnt[i];
        }
      }
    }
    for (int i = 0; i < 63; ++i) {
      if (cnt[i] > 0) {
        ans |= 1l << i;
      }
      cnt[i + 1] += cnt[i] / 2;
    }
    return ans;
  }
}

class Solution {
public:
  long long subsequenceSumOr(vector<int>& nums) {
    vector<long long> cnt(64);
    long long ans = 0;
    for (int v : nums) {
      for (int i = 0; i < 31; ++i) {
        if (v >> i & 1) {
          ++cnt[i];
        }
      }
    }
    for (int i = 0; i < 63; ++i) {
      if (cnt[i]) {
        ans |= 1ll << i;
      }
      cnt[i + 1] += cnt[i] / 2;
    }
    return ans;
  }
};

func subsequenceSumOr(nums []int) int64 {
  cnt := make([]int, 64)
  ans := 0
  for _, v := range nums {
    for i := 0; i < 31; i++ {
      if v>>i&1 == 1 {
        cnt[i]++
      }
    }
  }
  for i := 0; i < 63; i++ {
    if cnt[i] > 0 {
      ans |= 1 << i
    }
    cnt[i+1] += cnt[i] / 2
  }
  return int64(ans)
}