Question

2505. 所有子序列和的按位或

English Version

题目描述

给你一个整数数组 nums ，返回对数组中所有可能的 子序列 之和进行按位 或 运算后得到的值。

数组的 子序列 是从数组中删除零个或多个元素且不改变剩余元素的顺序得到的序列。

 

示例 1：

输入：nums = [2,1,0,3]
输出：7
解释：所有可能的子序列的和包括：0、1、2、3、4、5、6 。
由于 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7，所以返回 7 。

示例 2：

输入：nums = [0,0,0]
输出：0
解释：0 是唯一可能的子序列的和，所以返回 0 。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

解法

方法一：位运算

我们先用数组 $cnt$ 统计每一位上 $1$ 的个数，然后从低位到高位，如果该位上 $1$ 的个数大于 $0$，则将该位所表示的数加入到答案中。然后判断是否可以进位，是则累加到下一位。

时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别为数组长度和数组中元素的最大值。

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)
}