How hard is LeetCode 2505. Bitwise OR of All Subsequence Sums?

LeetCode 2505. Bitwise OR of All Subsequence Sums is rated Medium on LeetCode.

What is the time complexity of LeetCode 2505. Bitwise OR of All Subsequence Sums?

The Python solution on this page runs in O(n \times \log M), where n is the length of the array and M is the maximum value in the array.

What is the space complexity of LeetCode 2505. Bitwise OR of All Subsequence Sums?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2505. Bitwise OR of All Subsequence Sums cover?

LeetCode 2505. Bitwise OR of All Subsequence Sums is tagged Bit Manipulation, Brainteaser, Array, Math and Prefix Sum on LeetCode.

Is LeetCode 2505. Bitwise OR of All Subsequence Sums a premium problem?

Yes. LeetCode 2505. Bitwise OR of All Subsequence Sums is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Bitwise OR of All Subsequence Sums — LeetCode 2505 Python Solution

MediumLeetCode PremiumBit ManipulationBrainteaserArrayMathPrefix Sum

Problem: #2505
Pattern: Prefix Sum
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: nums = [2,1,0,3]
Output: 7
Explanation: All possible subsequence sums that we can have are: 0, 1, 2, 3, 4, 5, 6.

Python solution

Python

class Solution:
    def subsequenceSumOr(self, nums: List[int]) -> int:
        cnt = [0] * 64
        ans = 0
        for v in nums:
            for i in range(31):
                if (v >> i) & 1:
                    cnt[i] += 1
        for i in range(63):
            if cnt[i]:
                ans |= 1 << i
            cnt[i + 1] += cnt[i] // 2
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log M), where n is the length of the array and M is the maximum value in the array
Space	O(n) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2505. Bitwise OR of All Subsequence Sums is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2505. Bitwise OR of All Subsequence Sums?: LeetCode 2505. Bitwise OR of All Subsequence Sums is rated Medium on LeetCode.
What is the time complexity of LeetCode 2505. Bitwise OR of All Subsequence Sums?: The Python solution on this page runs in O(n \times \log M), where n is the length of the array and M is the maximum value in the array.
What is the space complexity of LeetCode 2505. Bitwise OR of All Subsequence Sums?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2505. Bitwise OR of All Subsequence Sums cover?: LeetCode 2505. Bitwise OR of All Subsequence Sums is tagged Bit Manipulation, Brainteaser, Array, Math and Prefix Sum on LeetCode.
Is LeetCode 2505. Bitwise OR of All Subsequence Sums a premium problem?: Yes. LeetCode 2505. Bitwise OR of All Subsequence Sums is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.