2044. Count Number of Maximum Bitwise-OR Subsets
Problem Description
In this problem, you're given an array of integers called nums. Your task is to find the maximum bitwise OR value that can be achieved by any non-empty subset of nums. The bitwise OR operation is a binary operation that takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. For two bits a and b, the result is 1 if either a or b is 1. Moreover, you need to determine how many unique non-empty subsets yield this maximum bitwise OR value.
To clarify the terms used:
- A subset of an array is formed by deleting zero or more elements from the array without changing the order of the remaining elements.
- Two subsets are considered different if they involve different indices of
nums. - The bitwise OR of an array is calculated by applying the OR operation to all its elements, starting with an initial value of
0. For example, if you have an array[a, b, c], the bitwise OR would bea OR b OR c.
So, if the input array is [3,1], there are three subsets: [3], [1], and [3,1]. The maximum bitwise OR value is 3 OR 1 = 3. There are two subsets ([3] and [3,1]) that have a bitwise OR of 3. Therefore, the answer would be 2.
Intuition
To solve this problem, we can apply a depth-first search (DFS) strategy.
The base intuition lies in understanding that the maximum bitwise OR of a set is bounded by the OR of the entire set. No subset can have a higher OR value than the OR of the entire set since adding more numbers can only maintain or increase the OR value.
With that in mind, calculate the OR of the entire array. This will be the maximum OR value (mx) that we're seeking subsets for.
Next, use a DFS function to explore all possible subsets. Start with an initial value t as 0 (the OR of an empty set) and iterate through the array. For each element at index i, you have two choices: either include nums[i] in the current subset or not. This leads to two recursive calls: one where you pass the current OR value unchanged, and another where you include nums[i] in the OR.
Keep track of how many times you reach the end of the array (i == len(nums)) with a subset OR value (t) equal to the maximum OR value (mx). Each time you reach this condition, increment your answer (ans), which keeps count of the number of subsets meeting the criteria.
After exploring all possibilities, ans will hold the number of subsets that have the maximal OR value, which is what the problem asks for.
Learn more about Backtracking patterns.
Which technique can we use to find the middle of a linked list?
Solution Approach
The implementation of the solution involves using a recursive function, dfs, which stands for depth-first search, to explore all possible subsets of the input array nums.
Here's a step-by-step breakdown of the algorithm:
-
Initialize the variable
mxto0. This will hold the maximum bitwise OR value that can be achieved by any subset ofnums. -
Go through each element in
numsand perform a bitwise OR operation betweenmxand the current element. Updatemxwith the result. After iterating over all elements,mxwill be the maximum bitwise OR value of the entire set ofnums. -
Define the recursive function
dfs(i, t). The parameterirepresents the current index in the arraynumsthat we're considering, andtis the current OR value of the subset being explored. -
Base case: If
iis equal to the length ofnums, we've explored a complete subset. Iftis equal tomx, increment the answeransby1, since we've found a subset with the maximum OR value. -
Recursive case: Make two recursive calls:
- The first call,
dfs(i + 1, t), explores the possibility of not including the current element (at indexi) in the subset, so we pass thetunchanged. - The second call,
dfs(i + 1, t | nums[i]), includes the current element in the subset and OR's it with the current valuet.
- The first call,
-
Start the DFS by calling
dfs(0, 0), considering an initially empty subset (OR value of0), and starting from index0. -
After all recursive calls are completed,
answill contain the number of different non-empty subsets with the maximum bitwise OR, which is then returned as the final result.
The algorithm effectively uses the DFS pattern to explore all subsets. It utilizes recursion to traverse the search tree where each node represents a potential subset with a specific OR value. The data structures used are simple integers to store the maximum OR value (mx) and the count of subsets (ans).
By using the DFS pattern, the solution ensures that all possible subsets are accounted for, without the need to explicitly generate and store each subset, making it an efficient approach to solving the problem.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Example Walkthrough
Let's consider an example array nums = [2, 5, 4] to illustrate the solution approach.
Step 1: Initialize mx
We initialize mx = 0. This will hold the maximum bitwise OR value.
Step 2: Compute Maximum Bitwise OR for Entire Array
We iterate through the nums array to compute the maximum bitwise OR value which is the OR of all elements.
mx = mx OR 2 = 0 OR 2 = 2mx = mx OR 5 = 2 OR 5 = 7mx = mx OR 4 = 7 OR 4 = 7
After this step, mx holds the value 7 which is the maximum bitwise OR value for the entire array.
Step 3: Define Recursive Function dfs(i, t)
We will define a recursive function dfs(i, t) to explore subsets. i represents the current index and t is the current OR value of the subset.
Step 4: Base Case to Count Valid Subsets
When i == len(nums), we check if t == mx. If yes, we found a valid subset and increment a counter.
Step 5: Recursive Case to Explore Subsets
We will consider two recursive calls starting from index 0:
- Not including the current element:
dfs(i + 1, t) - Including the current element:
dfs(i + 1, t | nums[i])
Step 6: Start DFS
We call dfs(0, 0) to start the exploration.
Recursive Exploration
Beginning with dfs(0, 0), we have an empty subset with an OR value of 0.
First call: dfs(1, 0 | 2) -> dfs(1, 2)
Second call: dfs(1, 0)
Now, from dfs(1, 2):
First call: dfs(2, 2 | 5) -> dfs(2, 7) (since 2 OR 5 = 7)
Second call: dfs(2, 2)
Similarly, dfs(1, 0) branches to dfs(2, 0 | 5) -> dfs(2, 5) and dfs(2, 0).
Continuing this process:
dfs(2, 7)branches todfs(3, 7 | 4) -> dfs(3, 7)anddfs(3, 7)dfs(2, 2)branches todfs(3, 2 | 4) -> dfs(3, 6)anddfs(3, 2)dfs(2, 5)branches todfs(3, 5 | 4) -> dfs(3, 5)anddfs(3, 5)dfs(2, 0)branches todfs(3, 0 | 4) -> dfs(3, 4)anddfs(3, 0)
Counting Valid Subsets
- When
i == len(nums), we check ift == mx(in this case,7). If yes, we found a valid subset. - For our example, the calls that end with
t == 7aredfs(3, 7),dfs(3, 7)(from bothdfs(2, 7)anddfs(2, 5)), which counts to3.
Conclusion
The subsets giving us the maximum OR of 7 are [2, 5], [5, 4], and [2, 5, 4]. After exploring all possible subsets recursively, we find that there are 3 non-empty subsets that yield the maximum bitwise OR value of 7. Thus, the solution for the array nums = [2, 5, 4] returns 3.
Solution Implementation
1from typing import List
2
3class Solution:
4 def countMaxOrSubsets(self, nums: List[int]) -> int:
5 # Initialize the maximum OR value and answer to zero.
6 max_or_value = answer = 0
7
8 # Compute the maximum OR value across all numbers in the list.
9 for num in nums:
10 max_or_value |= num
11
12 # Define the depth-first search function to explore all subsets.
13 def dfs(index, current_or):
14 nonlocal max_or_value, answer # Access variables from the outer scope.
15
16 # Base case: if the index is equal to the length of nums,
17 # we've considered all elements.
18 if index == len(nums):
19 # If the current OR is equal to the max OR value, increment the answer.
20 if current_or == max_or_value:
21 answer += 1
22 return
23
24 # Recursive call to explore the subset without including the current number.
25 dfs(index + 1, current_or)
26
27 # Recursive call to explore the subset including the current number.
28 dfs(index + 1, current_or | nums[index])
29
30 # Begin the depth-first search with the first index and an initial OR value of 0.
31 dfs(0, 0)
32
33 # Return the total count of subsets that have the maximum OR value.
34 return answer
35
36# The Solution can now be used to create an instance and call the countMaxOrSubsets method.
371class Solution {
2 private int maxOrValue; // Variable to store the maximum OR value of any subset.
3 private int count; // Counter for subsets equal to the maximum OR value.
4 private int[] nums; // Array to store the input numbers.
5
6 // Method to count the number of maximum OR subsets.
7 public int countMaxOrSubsets(int[] nums) {
8 maxOrValue = 0; // Initialize the maximum OR value.
9 // Calculate the maximum OR value by OR'ing all elements in the array.
10 for (int num : nums) {
11 maxOrValue |= num;
12 }
13 this.nums = nums; // Store the input array for further use in the method.
14 dfs(0, 0); // Start the Depth First Search (DFS) traversal.
15 return count; // Return the count of subsets with maximum OR value.
16 }
17
18 // Helper method to perform DFS traversal to find all subsets.
19 private void dfs(int index, int currentOr) {
20 // Base case: if we've considered all elements,
21 // check if the current OR equals the maximum OR value.
22 if (index == nums.length) {
23 if (currentOr == maxOrValue) {
24 count++; // Increment count if current subset OR equals max OR value.
25 }
26 return; // Return to explore other subsets.
27 }
28 // Exclude the current element and proceed to the next index.
29 dfs(index + 1, currentOr);
30 // Include the current element, OR it with the current value, and proceed.
31 dfs(index + 1, currentOr | nums[index]);
32 }
33}
341class Solution {
2public:
3 int maxOrValue; // To store the maximum OR value calculated from all numbers
4 int subsetCount; // To store the count of subsets whose OR equals maxOrValue
5 vector<int> numbers; // To store the input numbers
6
7 // Function to calculate the count of subsets whose bitwise OR equals the maximum OR of all numbers
8 int countMaxOrSubsets(vector<int>& nums) {
9 numbers = nums; // Initialize class member with input
10 maxOrValue = 0; // Initialize max OR value to 0
11 subsetCount = 0; // Initialize count of subsets to 0
12
13 // Calculate the maximum OR value from all the numbers
14 for (int x : nums) {
15 maxOrValue |= x;
16 }
17
18 // Start DFS traversal to explore all subsets and count those with max OR value
19 dfs(0, 0);
20
21 return subsetCount;
22 }
23
24 // Recursive function to perform DFS. It takes the current index and the accumulated OR value so far.
25 void dfs(int index, int currentOrValue) {
26 // Base case: if we have considered all elements
27 if (index == numbers.size()) {
28 // If the OR value equals the max OR value, increment the counter
29 if (currentOrValue == maxOrValue) {
30 subsetCount++;
31 }
32 return;
33 }
34
35 // Case 1: Exclude the current number from the subset and continue to the next element
36 dfs(index + 1, currentOrValue);
37
38 // Case 2: Include the current number in the subset (OR the current value with this number) and continue
39 dfs(index + 1, currentOrValue | numbers[index]);
40 }
41};
421function countMaxOrSubsets(nums: number[]): number {
2 // The total number of elements in the given array.
3 let totalElements = nums.length;
4 // Variable to store the maximum OR value across all subsets.
5 let maxOrValue = 0;
6 // Calculate the maximum OR value by iterating through the array.
7 for (let i = 0; i < totalElements; i++) {
8 maxOrValue |= nums[i];
9 }
10 // A count of subsets that have the maximum OR value.
11 let maxOrSubsetsCount = 0;
12
13 // Recursive helper function to perform depth-first search.
14 function dfs(currentOr: number, depth: number): void {
15 // If this is the end of the array, check if the current OR is the maximum OR.
16 if (depth == totalElements) {
17 if (currentOr == maxOrValue) {
18 // Increment the count if the current OR is equal to max OR.
19 maxOrSubsetsCount++;
20 }
21 return;
22 }
23 // case when the current number is not taken
24 dfs(currentOr, depth + 1);
25 // case when the current number is taken, it is ORed with the currentOr.
26 dfs(currentOr | nums[depth], depth + 1);
27 }
28
29 // Start the depth-first search with an initial OR value of 0 and at depth 0.
30 dfs(0, 0);
31
32 // Return the number of subsets that have the maximum OR value.
33 return maxOrSubsetsCount;
34}
35What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Time and Space Complexity
The given Python code defines the countMaxOrSubsets method that calculates the count of the maximum OR value subsets from a provided list of integers, nums.
Time Complexity
The time complexity of the algorithm is O(2^N), where N is the length of the nums list. This is because the algorithm uses a depth-first search approach to consider every possible subset of nums. In the worst case, every element is either included or excluded in a subset, leading to 2^N possible subsets.
The method dfs is called recursively twice for each element in the nums list - once to include the element in the current OR calculation (t | nums[i]) and once to exclude it (t). Hence, each call generates two more calls until the base case is reached when i equals the length of the nums.
Space Complexity
The space complexity is O(N) due to the recursive depth. In the worst-case scenario, the depth of the recursive call stack will be as deep as the number of elements in the list, since we are performing a depth-first search through the dfs function, and on each call to dfs, we are passing down a new index i which goes from 0 to N-1.
Additionally, two variables mx and ans are used, but their space usage is constant O(1) and does not depend on N, hence they don't contribute significantly to the space complexity.
It is important to note that the space complexity here refers to the auxiliary space, that is, the additional space excluding the space for the input itself.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.