Bitwise OR of All Subsequence Sums Solution in C++

Language Options

Code Solution


class Solution {
 public:
  long long subsequenceSumOr(vector& nums) {
    long ans = 0;
    long prefix = 0;

    for (const int num : nums) {
      prefix += num;
      ans |= num | prefix;
    }

    return ans;
  }
};

Problem Description

Welcome to the world of subsequences, where every combination of numbers is a potential candidate for a sum! The problem at hand, “Bitwise OR of All Subsequence Sums,” is like trying to find the best pizza topping combination for a party—everyone has their preferences, and you want to make sure you cover all bases.

Imagine you have a list of integers, and you need to find the Bitwise OR of all possible sums of subsequences. Sounds simple, right? Well, it’s like trying to remember every single pizza topping you’ve ever had while also trying to figure out which ones are the most popular. Spoiler alert: it’s a lot of work!

Approach

The provided code efficiently calculates the Bitwise OR of all subsequence sums by iterating through the list of numbers. It maintains a running total (prefix) of the sums and uses the Bitwise OR operation to combine the current number and the running total. This way, it ensures that all possible sums are considered without explicitly generating each subsequence.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

Real-World Example

Let’s say you’re at a buffet, and you want to try every possible combination of dishes. Each dish represents a number in your array. The Bitwise OR operation is like saying, “I’ll take a bit of everything!” By the end of your meal, you’ve created a unique flavor profile that represents all the combinations of dishes you’ve tried. Similarly, the solution combines all possible sums to give you a comprehensive result.