##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2505.html

# 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

• 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;
}
};

• 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


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