We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Bitwise OR of All Subsequence Sums

Number: 2644

Difficulty: Medium

Paid? Yes

Companies: Zomato

Problem Description

Given an integer array nums, return the bitwise OR of the sum of all possible subsequences in the array. A subsequence is a sequence that can be derived by removing zero or more elements without changing the order of the remaining elements.

For example, for nums = [2,1,0,3] the possible subsequence sums are 0, 1, 2, 3, 4, 5, 6 and their bitwise OR yields 7.

Key Insights

  • The brute force approach of enumerating all subsequences is infeasible due to the exponential number of subsequences.
  • Instead of generating every sum, analyze each bit position independently.
  • For any bit position, if at least one element in nums has that bit, then some subsequence sum will include that bit even if the total sum does not.
  • Thus, the final result can be computed as the bitwise OR of the total sum (which is the sum of all array elements) and the bitwise OR of all individual elements.
  • Mathematically, answer = (sum(nums)) OR (bitwise OR of nums).

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums (we do two traversals of the array). Space Complexity: O(1), as only a few integer variables are used.

Solution

The solution computes two values:

  1. totalSum: the sum of all elements in nums.
  2. orAll: the bitwise OR of all elements in nums.

The final answer is obtained by performing a bitwise OR between totalSum and orAll.

This works because:

  • totalSum represents the maximum possible sum (from taking all elements).
  • orAll captures all bits that appear in any element.
  • Any bit that appears in any element will appear in at least one subsequence sum; hence combining these two captures every bit that could be set in one of the subsequence sums.

Code Solutions

# Function that returns the bitwise OR of all subsequence sums
def subsequenceBitwiseOR(nums):
    # Initialize variables for total sum and bitwise OR of all numbers
    total_sum = 0
    all_or = 0
    
    # Iterate over each number in the list
    for num in nums:
        total_sum += num       # Accumulate the total sum
        all_or |= num          # Accumulate the OR of all numbers
    
    # Final answer is the bitwise OR of total_sum and all_or
    return total_sum | all_or

# Example test case
nums = [2, 1, 0, 3]
print(subsequenceBitwiseOR(nums))  # Expected output 7
← Back to All Questions