#2505
Medium Algorithms Bitwise or of all subsequence sums
Array Math Bit Manipulation Brainteaser Prefix Sum
64.2% acceptance
Mar 31, 2026
55
17
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.
Solution
Rust
Time O(n²)
Space O(1)
impl Solution {
pub fn subsequence_sum_or(nums: Vec<i32>) -> i64 {
let mut counts = [0i64; 64];
for &num in &nums {
for b in 0..30 {
if (num >> b) & 1 == 1 {
counts[b] += 1;
}
}
}
let mut result: i64 = 0;
let mut carry: i64 = 0;
for b in 0..64 {
let total = counts[b] + carry;
if total > 0 {
result |= 1i64 << b;
}
carry = total / 2;
}
result
}
}