very lenthy and tricky approach can refer to below code int solve(int i, int ors, int maxi, vector& nums) { if(i >= nums.size()){ // Base case: if OR of the current subset equals the maximum OR, count it return (ors == maxi) ? 1 : 0; } // Include the current element in the subset OR int cnt = 0; cnt += solve(i + 1, ors | nums[i], maxi, nums);
// Exclude the current element from the subset OR cnt += solve(i + 1, ors, maxi, nums);
return cnt; } // Function to count the number of subsets with maximum OR value int countMaxOrSubsets(vector& nums) { int maxi = 0;
// Calculate the maximum OR value from all elements for(auto it: nums){ maxi |= it; } // Start recursion from the first element with OR = 0 return solve(0, 0, maxi, nums); }
class Solution { public: int solve(vector& nums, int idx, int currOR, int maxOR, vector& mem) { // Base case: if we've gone through all elements if (idx >= nums.size()) { // Check if the current OR equals the maximum OR return currOR == maxOR ? 1 : 0; } // If the result for this state is already computed, return it if (mem[idx][currOR] != -1) { return mem[idx][currOR]; } // Option 1: Exclude the current element int exclude = solve(nums, idx + 1, currOR, maxOR, mem); // Option 2: Include the current element and update OR value int include = solve(nums, idx + 1, currOR | nums[idx], maxOR, mem); // Store the result in memoization table and return return mem[idx][currOR] = exclude + include; } int countMaxOrSubsets(vector& nums) { int maxOR = 0; // Calculate the maximum possible OR across all numbers for (int& ele : nums) { maxOR |= ele; } // Memoization table to store intermediate results int n = nums.size(); vector mem(n, vector(maxOR + 1, -1)); // Start the recursive process from index 0 and initial OR value 0 return solve(nums, 0, 0, maxOR, mem); } };
for me this is the hard level question. Thank you sir for your explanation :)
wlecome :)
very lenthy and tricky approach
can refer to below code
int solve(int i, int ors, int maxi, vector& nums) {
if(i >= nums.size()){
// Base case: if OR of the current subset equals the maximum OR, count it
return (ors == maxi) ? 1 : 0;
}
// Include the current element in the subset OR
int cnt = 0;
cnt += solve(i + 1, ors | nums[i], maxi, nums);
// Exclude the current element from the subset OR
cnt += solve(i + 1, ors, maxi, nums);
return cnt;
}
// Function to count the number of subsets with maximum OR value
int countMaxOrSubsets(vector& nums) {
int maxi = 0;
// Calculate the maximum OR value from all elements
for(auto it: nums){
maxi |= it;
}
// Start recursion from the first element with OR = 0
return solve(0, 0, maxi, nums);
}
Nice
Thanks :)
class Solution {
public:
int solve(vector& nums, int idx, int currOR, int maxOR, vector& mem) {
// Base case: if we've gone through all elements
if (idx >= nums.size()) {
// Check if the current OR equals the maximum OR
return currOR == maxOR ? 1 : 0;
}
// If the result for this state is already computed, return it
if (mem[idx][currOR] != -1) {
return mem[idx][currOR];
}
// Option 1: Exclude the current element
int exclude = solve(nums, idx + 1, currOR, maxOR, mem);
// Option 2: Include the current element and update OR value
int include = solve(nums, idx + 1, currOR | nums[idx], maxOR, mem);
// Store the result in memoization table and return
return mem[idx][currOR] = exclude + include;
}
int countMaxOrSubsets(vector& nums) {
int maxOR = 0;
// Calculate the maximum possible OR across all numbers
for (int& ele : nums) {
maxOR |= ele;
}
// Memoization table to store intermediate results
int n = nums.size();
vector mem(n, vector(maxOR + 1, -1));
// Start the recursive process from index 0 and initial OR value 0
return solve(nums, 0, 0, maxOR, mem);
}
};
nice :)