Bitwise OR of All Subsequence Sums - Practice Coding Problems

Bitwise OR of All Subsequence Sums - Problem

Array Math Bit Manipulation Brainteaser Prefix Sum Medium

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.

For example, given array [1, 2, 3], the subsequences are: [] (sum=0), [1] (sum=1), [2] (sum=2), [3] (sum=3), [1,2] (sum=3), [1,3] (sum=4), [2,3] (sum=5), [1,2,3] (sum=6). The bitwise OR of all these sums is 0 | 1 | 2 | 3 | 3 | 4 | 5 | 6 = 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1, 2]

› Output: 3

💡 Note: Subsequences: [] (sum=0), [1] (sum=1), [2] (sum=2), [1,2] (sum=3). OR of sums: 0 | 1 | 2 | 3 = 3

Example 2 — Single Element

$ Input: nums = [5]

› Output: 5

💡 Note: Subsequences: [] (sum=0), [5] (sum=5). OR of sums: 0 | 5 = 5

Example 3 — Three Elements

$ Input: nums = [1, 2, 4]

› Output: 7

💡 Note: All possible sums: 0,1,2,3,4,5,6,7. OR of all sums: 0|1|2|3|4|5|6|7 = 7

Constraints

1 ≤ nums.length ≤ 20
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1, 2] with all possible subsequences

Calculate Sums

Find sum of each subsequence: 0, 1, 2, 3

Bitwise OR

OR all sums together: 0 | 1 | 2 | 3 = 3

Key Takeaway

🎯 Key Insight: The bitwise OR captures all bit positions that can be set by any possible subsequence sum

Asked in

G Google 15 f Meta 12 M Microsoft 8

The key insight is that we need to find all possible subsequence sums and take their bitwise OR. The dynamic programming approach efficiently builds the set of achievable sums without generating duplicate subsequences. Time: O(n × S), Space: O(S) where S is the sum of all elements.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Subsequences	O(n × 2ⁿ)	O(1)	Generate all 2^n subsequences and calculate their sums
Dynamic Programming with Set	O(n × S)	O(S)	Track all achievable sums using dynamic programming

Generate All Subsequences — Algorithm Steps

Generate all 2^n subsequences using bit masks
Calculate sum for each subsequence
Take bitwise OR of all sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Array

Start with input array [1, 2]

Generate Subsequences

Create all 2^n = 4 subsequences

Calculate OR

OR all sums: 0 | 1 | 2 | 3 = 3

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    int result = 0;
    
    // Generate all 2^n subsequences using bit masks
    for (int mask = 0; mask < (1 << n); mask++) {
        int subsequenceSum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subsequenceSum += nums[i];
            }
        }
        result |= subsequenceSum;
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array
    int nums[20];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 20) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

2^n subsequences, each requiring O(n) time to calculate sum

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current sum and result

✓ Linear Space

23.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler