2505. Bitwise OR of All Subsequence Sums
Problem Description
This problem requests the calculation of a special value derived from all possible subsequence sums of an integer array nums
. To explain further, a subsequence is a series of numbers that come from the original array either entirely or after removing some elements, but with the original order preserved. An empty subsequence is also considered valid. The special value that the problem requires is the bitwise OR of all the unique subsequence sums.
For instance, given an array [1,2]
, the subsequences are [1]
, [2]
, and [1,2]
, plus the empty subsequence []
. The sum of these subsequences are 1
, 2
, 3
, and 0
respectively. The bitwise OR of these sums (1 | 2 | 3 | 0
) equals 3
.
The problem's complexity comes from the potentially large number of subsequences, which increases exponentially with the size of the array. The challenge is to find an efficient way to compute the special value without having to actually generate and sum every possible subsequence.
Intuition
To devise a solution to the problem without generating every possible subsequence (which would be computationally expensive), we observe that each bit position in the integers can be treated independently due to the properties of the bitwise OR operator.
Here's the intuition behind the solution:
- Initialize a counter array,
cnt
, which will keep track of the number of times a bit is set at different positions across all numbers in the array. - Iterate through each number
v
in the arraynums
. For each bit positioni
, check if thei
th bit ofv
is set (i.e., equals 1). If so, increment the count incnt[i]
. - Initialize a variable
ans
, which will hold the final answer. - Iterate through the counter array
cnt
. If at any bit positioni
,cnt[i]
is non-zero, it implies that this bit appeared in our subsequence sum. Thus, set thei
th bit inans
to 1 by performing a bitwise OR betweenans
and1
shiftedi
times to the left. - Additionally, we carry over half of the count from each bit position to the next higher position by adding
cnt[i] // 2
tocnt[i + 1]
. This represents the combination of bits when we add numbers together, as bits carry when there is a sum of1 + 1 = 10
in binary. - The loop iterates up to 63, as it accounts for the carry that could propagate through all 32 bit positions twice (since every addition might cause a carry to the next position).
- The variable
ans
now contains the bitwise OR of all the possible subsequence sums, which is the required answer.
The solution leverages the fact that we can analyze and manipulate the bits of the entire array rather than individual subsequences. It counts bit occurrences and then uses those counts to determine which bits will definitely be set in the final OR result. The carrying of half the count to the next bit position simulates how bit addition would occur across all subsequence sums.
Learn more about Math patterns.
Solution Approach
The implementation of the solution is based on bit manipulation and the understanding of how bitwise OR and sum operations interact with each other on the binary level.
Here's a detailed walk through of the solution code:
-
The solution declares a
Solution
class with a method calledsubsequenceSumOr
, which accepts an arraynums
. -
Inside this method, a
cnt
array with 64 elements initialized to 0 is created. This array is used to count the occurrences of set bits in the binary representation of all numbers innums
. It reserves enough space to handle the bit carry operations that can happen as we simulate adding the numbers together.
cnt = [0] * 64
- The
ans
variable is initialized to 0. This variable will hold the result of the bitwise OR of all possible subsequence sums.
ans = 0
- The solution runs a loop over each number
v
in thenums
array and then a nested loop over each bit positioni
, starting from 0 up to 30 (inclusive), which is sufficient to cover the bit-positions for a 32 bit integer.
for v in nums:
for i in range(31):
- If the
i
th bit ofv
is set (i.e.,v >> i
bitwise right shifti
and bitwise AND with 1 gives us thei
th bit), the corresponding count incnt[i]
is incremented.
if (v >> i) & 1: cnt[i] += 1
- After the counts are determined, the solution iterates over all 63 possible bit positionsāenough to account for carry-over during addition. For each
i
, ifcnt[i]
is non-zero,1 << i
(bitwise left shift, which effectively is2^i
) is bitwise ORed withans
. This sets thei
th bit ofans
because that bit will appear in at least one subsequence sum.
for i in range(63):
if cnt[i]:
ans |= 1 << i
- The solution also ensures that the number of times a bit is carried over to the next higher position is taken into account by adding
cnt[i] // 2
tocnt[i + 1]
. This simulates the carry-over process in binary addition across all subsequence sums.
cnt[i + 1] += cnt[i] // 2
- Finally,
ans
is returned. It now holds the value of the bitwise OR of the sum of all possible subsequences.
return ans
The implementation successfully leverages bit manipulation to efficiently solve a problem that would otherwise require an impractical brute-force approach due to the exponentially growing number of subsequences in the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the integer array [3,5]
to illustrate the solution approach:
-
We initialize a counter array
cnt
of 64 elements to keep track of the number of set bits at each bit position:cnt = [0] * 64
-
We create
ans
variable, initialized to0
, which will store our answer:ans = 0
-
We iterate over each value
v
innums
(3
and5
), and for each value, we iterate over each bit positioni
from 0 to 30:nums = [3, 5] for v in nums: for i in range(31): if (v >> i) & 1: cnt[i] += 1
-
Binary representations for
3
and5
are011
and101
respectively.After iterating through the array, our
cnt
array will have the counts for each bit position:index: 0 1 2 ... cnt: [0, 2, 1, ...] # Only showing relevant bits
Here, the bit at index
1
occurred twice (1
from both3
and5
), and the bit at index2
occurred once (from5
). -
We then iterate through the counter
cnt
and update theans
variable with the bitwise OR operation for any non-zero counts, also handling the carry over:for i in range(63): if cnt[i]: ans |= 1 << i cnt[i + 1] += cnt[i] // 2
In this process, the
ans
variable will be updated as follows:loop i=1: ans |= 1 << 1 # as cnt[1] had a count of 2 ans now becomes 2 loop i=2: ans |= 1 << 2 # as cnt[2] had a count of 1 ans now becomes 6
Simultaneously, the carry over for the next position is handled:
cnt[2] += cnt[1] // 2 cnt array becomes [0, 0, 2, ...] after carry, showing we carried 1 to the next significant bit.
-
The final value of
ans
is6
, which is the bitwise OR of sum of all possible subsequences of the array[3,5]
.
The returned result from our example array [3,5]
is 6
, which corroborates with the computation of the subsequence sums:
[]
sum is0
,[3]
sum is3
,[5]
sum is5
,[3,5]
sum is8
.
The bitwise OR of all sums (0 | 3 | 5 | 8
) is indeed 6
. This example walk-through shows how the bit manipulation approach efficiently calculates the special value without having to enumerate all subsequences.
Solution Implementation
1from typing import List
2
3class Solution:
4 def subsequenceSumOr(self, nums: List[int]) -> int:
5 # Array to count the number of times each bit is set in all numbers
6 bit_count = [0] * 64
7 # Store the final result - sum of ORs of all subsequences
8 result = 0
9
10 # Count the number of times each bit is set across all numbers
11 for value in nums:
12 for i in range(31):
13 if (value >> i) & 1: # Check if the i-th bit of value is set'
14 bit_count[i] += 1
15
16 # Iterate over the bit counts to compute the result
17 for i in range(63): # Use 63 because we're carrying over the bits to higher bits
18 if bit_count[i]:
19 result |= 1 << i # OR the result with the bit set if it's count is non-zero
20 bit_count[i + 1] += bit_count[i] // 2 # Carry over half the count to the next higher bit
21
22 return result
23
1class Solution {
2
3 public long subsequenceSumOr(int[] nums) {
4 long[] bitCounts = new long[64]; // Array to store the count of set bits at each position
5 long answer = 0; // Variable to store the final OR sum of all subsequences
6
7 // Count the occurrence of each bit among the numbers
8 for (int value : nums) {
9 for (int i = 0; i < 31; ++i) {
10 // Check the i-th bit of the number
11 if (((value >> i) & 1) == 1) {
12 // If it's set, increment the count of this bit in the array
13 ++bitCounts[i];
14 }
15 }
16 }
17
18 // Calculate the OR sum by combining bits present in the subsequences
19 for (int i = 0; i < 63; ++i) { // Iterate through all but the last element of the bitCounts array
20 if (bitCounts[i] > 0) {
21 answer |= 1L << i; // Use bitwise OR to set the bits in the answer
22 }
23 // Propagate the carry-over of counting bits to the next higher bit
24 bitCounts[i + 1] += bitCounts[i] / 2;
25 }
26
27 // Return the calculated OR sum
28 return answer;
29 }
30}
31
1class Solution {
2public:
3 // Function to calculate the sum of bitwise OR of all subsequence.
4 long long subsequenceSumOr(vector<int>& nums) {
5 vector<long long> bitCounts(64); // To store count of set bits for each bit position
6 long long ans = 0; // To store the result of sum of the bitwise OR of all subsequences
7
8 // Counting set bits for every position in all numbers
9 for (int num : nums) {
10 for (int i = 0; i < 31; ++i) { // Loop through each bit position
11 if (num & (1 << i)) { // Check if the ith bit is set
12 ++bitCounts[i]; // Increment count for this bit position
13 }
14 }
15 }
16
17 // Calculating the sum of the bitwise OR of all subsequences using the bit counts
18 for (int i = 0; i < 63; ++i) { // Loop through up to the second-to-last bit position
19 if (bitCounts[i]) {
20 ans |= 1LL << i; // Update result with the ith bit set if count is not zero
21 }
22 // Since any set bit will contribute to two subsequences when paired with another bit,
23 // we add half the count of the current bit to the next bit.
24 bitCounts[i + 1] += bitCounts[i] / 2;
25 }
26
27 return ans; // Return the final sum
28 }
29};
30
1// A function to calculate the sum of bitwise OR of all subsequence.
2function subsequenceSumOr(nums: number[]): number {
3 let bitCounts: number[] = new Array(64).fill(0); // To store count of set bits for each bit position.
4 let ans: number = 0; // To store the result of sum of the bitwise OR of all subsequences.
5
6 // Counting set bits for every position in all numbers.
7 nums.forEach(num => {
8 for (let i = 0; i < 31; i++) { // Loop through each bit position.
9 if (num & (1 << i)) { // Check if the i-th bit is set.
10 bitCounts[i]++; // Increment count for this bit position.
11 }
12 }
13 });
14
15 // Calculating the sum of bitwise OR of all subsequences using the bit counts.
16 for (let i = 0; i < 63; i++) { // Loop through up to the second-to-last bit position.
17 if (bitCounts[i] > 0) {
18 ans |= 1 << i; // Update result with the i-th bit set if count is not zero.
19 }
20 // Since any set bit will contribute to two subsequences when paired with another bit,
21 // we add half the count of the current bit to the next bit.
22 bitCounts[i + 1] += Math.floor(bitCounts[i] / 2);
23 }
24
25 return ans; // Return the final sum.
26}
27
Time and Space Complexity
Time Complexity
The time complexity of the provided code is determined by the number of loops and operations within each loop:
- The outer loop runs for each element in the
nums
list, thus it isO(n)
wheren
is the length of the list. - The inner loop runs for a constant 31 times (assumes 32-bit integer processing), which is
O(1)
with respect to the input size.
Since the inner loop is nested within the outer loop, we multiply the complexities of two loops, which results in O(n) * O(1)
, leading to a final time complexity of O(n)
.
Space Complexity
The space complexity of the code consists of:
- The space used by the
cnt
array, which has a fixed size of 64, thusO(1)
. - The
ans
variable, which also occupies a constant space and does not depend on the input size.
Considering both of these together, the overall space complexity of the provided code is O(1)
since the extra space required does not scale with the size of the input (n
).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!