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 1:
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. And we have 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7, so we return 7.
Example 2:
Input: nums = [0,0,0] Output: 0 Explanation: 0 is the only possible subsequence sum we can have, so we return 0.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109We first use an array cnt to count the number of 1s in each bit position. Then, from the lowest bit to the highest bit, if the number of 1s in that bit position is greater than 0, we add the value represented by that bit to the answer. Then, we check if there can be a carry-over, and if so, we add it to the next bit.
The time complexity is O(n times log M), where n is the length of the array and M is the maximum value in the array.
Java
C++
Go
L6. Recursion on Subsequences | Printing Subsequences • take U forward • 747,416 views views
Watch 9 more video solutions →Practice Bitwise OR of All Subsequence Sums with our built-in code editor and test cases.
Practice on FleetCode