aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-27 18:53:39 -0600
committerJack Sangdahl <[email protected]>2025-07-27 18:53:39 -0600
commit59613ec9d3a899b43dd9c788cb1c0d14719eff76 (patch)
treefe203e24715cf92d9753f1ac4571a9975232167e
parentf031d94a96ae6ea157da22dac6b7f533b18f5f9c (diff)
downloadleetcode-59613ec9d3a899b43dd9c788cb1c0d14719eff76.tar.gz
leetcode-59613ec9d3a899b43dd9c788cb1c0d14719eff76.zip
2044. count number of maximum bitwise or subsets
-rw-r--r--count_num_max_or_subset.c34
-rw-r--r--count_num_max_or_subset.py22
2 files changed, 21 insertions, 35 deletions
diff --git a/count_num_max_or_subset.c b/count_num_max_or_subset.c
index 1b5a160..8b24f1b 100644
--- 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
index 02aa433..c19e4e1 100644
--- 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]))