diff options
author | Jack Sangdahl <[email protected]> | 2024-10-17 19:11:55 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-17 19:11:55 -0600 |
commit | dbd535bd9e0d0803402c944cd40e33229dd9a0c1 (patch) | |
tree | 4072ab3f1ef81444970a7fdbef62bd7cae96144d | |
parent | c65e70966f48d5b5b6ad4be8912cb0054b9b2978 (diff) | |
download | leetcode-dbd535bd9e0d0803402c944cd40e33229dd9a0c1.tar.gz leetcode-dbd535bd9e0d0803402c944cd40e33229dd9a0c1.zip |
2044. count number of maximum bitwise-or subsets
-rw-r--r-- | count_num_max_or_subset.c | 43 | ||||
-rw-r--r-- | count_num_max_or_subset.py | 32 |
2 files changed, 75 insertions, 0 deletions
diff --git a/count_num_max_or_subset.c b/count_num_max_or_subset.c new file mode 100644 index 0000000..1b5a160 --- /dev/null +++ b/count_num_max_or_subset.c @@ -0,0 +1,43 @@ +// 2044. Count Number of Maximum Bitwise-OR Subsets +#include "leetcode.h" + +/* + * 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 + * 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) + */ + +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]; + for (int i = 0; i < numsSize; i++) { + if (nums[i] == max) + ans++; + backtrack(nums, numsSize, max, nums[i], i + 1, &ans); + } + return ans; +} + +int main() { + int n1[] = {3, 1}, n2[] = {2, 2, 2}, n3[] = {3, 2, 1, 5}; + printf("%d\n", countMaxOrSubsets(n1, ARRAY_SIZE(n1))); // expect: 2 + printf("%d\n", countMaxOrSubsets(n2, ARRAY_SIZE(n2))); // expect: 7 + printf("%d\n", countMaxOrSubsets(n3, ARRAY_SIZE(n3))); // expect: 6 +} diff --git a/count_num_max_or_subset.py b/count_num_max_or_subset.py new file mode 100644 index 0000000..02aa433 --- /dev/null +++ b/count_num_max_or_subset.py @@ -0,0 +1,32 @@ +# 2044. Count Number of Maximum Bitwise-OR Subsets +from collections import Counter + +""" +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 +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) +""" + + +class Solution(object): + def countMaxOrSubsets(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + dp = Counter([0]) + for n in nums: + for i, j in list(dp.items()): + dp[i | n] += j + 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])) |