Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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
  }
}