2044. Count Number of Maximum Bitwise-OR Subsets

[mah-shamim]

Topics: Array, Backtracking, Bit Manipulation, Enumeration

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

Example 1:

• Input: nums = [3,1]
• Output: 2
• Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
  • [3]
  • [3,1]

Example 2:

• Input: nums = [2,2,2]
• Output: 7
• Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.

Example 3:

• Input: nums = [3,2,1,5]
• Output: 6
• Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
  • [3,5]
  • [3,1,5]
  • [3,2,5]
  • [3,2,1,5]
  • [2,5]
  • [2,1,5]

Constraints:

• 1 <= nums.length <= 16
• 1 <= nums[i] <= 105

Hint:

1. Can we enumerate all possible subsets?
2. The maximum bitwise-OR is the bitwise-OR of the whole array.

[kovatz]

We can follow these steps:

1. Calculate the Maximum Bitwise OR: The maximum bitwise OR of a subset can be determined by performing a bitwise OR operation across all elements of the array. This gives us the maximum possible bitwise OR.

2. Enumerate All Subsets: Since the size of the array is small (up to 16), we can enumerate all possible subsets using a bit manipulation technique. For an array of size n, there are 2^n possible subsets.

3. Count Valid Subsets: For each subset, compute its bitwise OR and check if it matches the maximum bitwise OR. If it does, increment a counter.

Let's implement this solution in PHP: 2044. Count Number of Maximum Bitwise-OR Subsets

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function countMaxBitwiseORSubsets($nums) {
    // Step 1: Calculate the maximum bitwise OR of the entire array
    $maxOR = 0;
    foreach ($nums as $num) {
        $maxOR |= $num; // Bitwise OR operation
    }
    
    // Step 2: Initialize the count of valid subsets
    $count = 0;
    $n = count($nums);
    
    // Step 3: Enumerate all subsets using bit manipulation
    // There are 2^n subsets, we loop from 1 to (2^n) - 1 to skip the empty subset
    for ($i = 1; $i < (1 << $n); $i++) {
        $currentOR = 0;
        for ($j = 0; $j < $n; $j++) {
            // Check if the j-th bit is set in i
            if ($i & (1 << $j)) {
                $currentOR |= $nums[$j]; // Include this element in the subset
            }
        }
        // Step 4: Check if the current subset's OR equals maxOR
        if ($currentOR == $maxOR) {
            $count++;
        }
    }
    
    return $count;
}

// Example usage
$nums1 = [3, 1];
echo countMaxBitwiseORSubsets($nums1) . "\n"; // Output: 2

$nums2 = [2, 2, 2];
echo countMaxBitwiseORSubsets($nums2) . "\n"; // Output: 7

$nums3 = [3, 2, 1, 5];
echo countMaxBitwiseORSubsets($nums3) . "\n"; // Output: 6
?>

Explanation:

1. Maximum Bitwise OR Calculation:

   • We use a loop to calculate the maximum bitwise OR of the array by performing a bitwise OR on each element.

2. Subset Enumeration:

   • We loop through all numbers from 1 to 2^n - 1 (where n is the length of nums), representing all non-empty subsets.
   • For each number, we check each bit to see which elements are included in the subset.

3. Valid Subset Count:

   • After calculating the bitwise OR for the current subset, we check if it equals maxOR. If it does, we increment our counter.

This solution is efficient given the constraints and should work well for arrays of size up to 16, resulting in at most 65,535 subsets to evaluate.

[mah-shamim]

Thanks to solve the problem of counting the number of maximum bitwise OR subsets in a given array

[kovatz]

Thanks