leetcode

commit 59613ec9d3a899b43dd9c788cb1c0d14719eff76
parent f031d94a96ae6ea157da22dac6b7f533b18f5f9c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 27 Jul 2025 18:53:39 -0600

2044. count number of maximum bitwise or subsets

Diffstat:
M
count_num_max_or_subset.c
 | 
34
++++++++++------------------------
M
count_num_max_or_subset.py
 | 
22
+++++++++++-----------

2 files changed, 21 insertions(+), 35 deletions(-)
diff --git a/count_num_max_or_subset.c b/count_num_max_or_subset.c
@@ -2,37 +2,23 @@
 #include "leetcode.h"
 
 /*
- * given an integer array 'nums', find the maximum possible bitwise OR of a
+ * 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 0) elements of 'b'. two
+ * 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 bitwose OR of an array 'a' is equal to 'a[0] | a[1] | ... |
- * a[n]' (0-indexed)
+ * different. the bitwise or of an array 'a' is equal to 'a[0] | a[1] | ... |
+ * a[a.length - 1]'
  */
 
-void backtrack(int *nums, int numsSize, int target, int idx, int pos,
-               int *res) {
-  if (pos == numsSize)
-    return;
-  for (int i = pos; i < numsSize; i++) {
-    int tmp = idx | nums[i];
-    if (tmp == target)
-      (*res)++;
-    backtrack(nums, numsSize, target, tmp, i + 1, res);
-  }
-}
-
 int countMaxOrSubsets(int *nums, int numsSize) {
-  int max = 0, ans = 0;
-  for (int i = 0; i < numsSize; i++)
-    max |= nums[i];
+  int max = 0, dp[1 << 17] = {1};
   for (int i = 0; i < numsSize; i++) {
-    if (nums[i] == max)
-      ans++;
-    backtrack(nums, numsSize, max, nums[i], i + 1, &ans);
+    for (int j = max; j >= 0; --j)
+      dp[j | nums[i]] += dp[j];
+    max |= nums[i];
   }
-  return ans;
+  return dp[max];
 }
 
 int main() {
diff --git a/count_num_max_or_subset.py b/count_num_max_or_subset.py
@@ -2,13 +2,13 @@
 from collections import Counter
 
 """
-given an integer array 'nums', find the maximum possible bitwise OR of a
+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 0) elements of 'b'. two
+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 bitwose OR of an array 'a' is equal to 'a[0] | a[1] | ... |
-a[n]' (0-indexed)
+different. the bitwise or of an array 'a' is equal to 'a[0] | a[1] | ... |
+a[a.length - 1]'
 """
 
 
@@ -19,14 +19,14 @@ class Solution(object):
         :rtype: int
         """
         dp = Counter([0])
-        for n in nums:
-            for i, j in list(dp.items()):
-                dp[i | n] += j
+        for i in nums:
+            for k, v in dp.items():
+                dp[k | i] += v
         return dp[max(dp)]
 
 
 if __name__ == "__main__":
     obj = Solution()
-    print(obj.countMaxOrSubsets([3, 1]))
-    print(obj.countMaxOrSubsets([2, 2, 2]))
-    print(obj.countMaxOrSubsets([3, 2, 1, 5]))
+    print(obj.countMaxOrSubsets(nums=[3, 1]))
+    print(obj.countMaxOrSubsets(nums=[2, 2, 2]))
+    print(obj.countMaxOrSubsets(nums=[3, 2, 1, 5]))