Count Number of Maximum Bitwise OR Subsets | Recursion DP | Leetcode 2044

[@sailendrachettri8521]

for me this is the hard level question. Thank you sir for your explanation :)

[@techdose4u]

wlecome :)

[@RiteshKumar-IIT_KGP]

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);
}

[@shivnathkahar8985]

Nice

[@techdose4u]

Thanks :)

[@jitinsaxena3239]

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);
}
};

[@techdose4u]

nice :)