{"id":8610,"date":"2021-10-17T20:54:32","date_gmt":"2021-10-18T03:54:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8610"},"modified":"2021-10-17T20:55:20","modified_gmt":"2021-10-18T03:55:20","slug":"leetcode-2044-count-number-of-maximum-bitwise-or-subsets","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-2044-count-number-of-maximum-bitwise-or-subsets\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets"},"content":{"rendered":"\n

Given an integer array nums<\/code>, find the maximum<\/strong> possible bitwise OR<\/strong> of a subset of nums<\/code> and return the number of different non-empty subsets<\/strong> with the maximum bitwise OR<\/em>.<\/p>\n\n\n\n

An array a<\/code> is a subset<\/strong> of an array b<\/code> if a<\/code> can be obtained from b<\/code> by deleting some (possibly zero) elements of b<\/code>. Two subsets are considered different<\/strong> if the indices of the elements chosen are different.<\/p>\n\n\n\n

The bitwise OR of an array a<\/code> is equal to a[0] OR<\/strong> a[1] OR<\/strong> ... OR<\/strong> a[a.length - 1]<\/code> (0-indexed<\/strong>).<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [3,1]\nOutput:<\/strong> 2\nExplanation:<\/strong> The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:\n- [3]\n- [3,1]\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,2,2]\nOutput:<\/strong> 7\nExplanation:<\/strong> All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23<\/sup> - 1 = 7 total subsets.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [3,2,1,5]\nOutput:<\/strong> 6\nExplanation:<\/strong> The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:\n- [3,5]\n- [3,1,5]\n- [3,2,5]\n- [3,2,1,5]\n- [2,5]\n- [2,1,5]<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 16<\/code><\/li>
  • 1 <= nums[i] <= 105<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Try all possible subsets<\/p>\n\n\n\n
    Time complexity: O(n*2n<\/sup>)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countMaxOrSubsets(vector& nums) {\n    const int n = nums.size();\n    int max_or = 0;\n    int count = 0;\n    for (int s = 0; s < 1 << n; ++s) {\n      int cur_or = 0;\n      for (int i = 0; i < n; ++i)\n        if (s >> i & 1) cur_or |= nums[i];\n      if (cur_or > max_or) {\n        max_or = cur_or;\n        count = 1;\n      } else if (cur_or == max_or) {\n        ++count;\n      }\n    }\n    return count;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[122,177,493],"class_list":["post-8610","post","type-post","status-publish","format-standard","hentry","category-searching","tag-combination","tag-medium","tag-subset","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8610","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8610"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8610\/revisions"}],"predecessor-version":[{"id":8612,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8610\/revisions\/8612"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8610"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8610"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8610"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}