Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2275.html
2275. Largest Combination With Bitwise AND Greater Than Zero
- Difficulty: Medium.
- Related Topics: Array, Hash Table, Bit Manipulation, Counting.
- Similar Questions: Count Number of Maximum Bitwise-OR Subsets.
Problem
The bitwise AND of an array nums
is the bitwise AND of all integers in nums
.
-
For example, for
nums = [1, 5, 3]
, the bitwise AND is equal to1 & 5 & 3 = 1
. -
Also, for
nums = [7]
, the bitwise AND is7
.
You are given an array of positive integers candidates
. Evaluate the bitwise AND of every combination of numbers of candidates
. Each number in candidates
may only be used once in each combination.
Return the size of the **largest combination of candidates
with a bitwise AND greater than **0
.
Example 1:
Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.
Example 2:
Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.
Constraints:
-
1 <= candidates.length <= 105
-
1 <= candidates[i] <= 107
Solution (Java, C++, Python)
-
class Solution { public int largestCombination(int[] candidates) { int[] bits = new int[32]; for (int x : candidates) { for (int i = 0; x != 0; i++, x >>= 1) { bits[i] += x & 1; } } int ans = 0; for (int b : bits) { ans = Math.max(ans, b); } return ans; } } ############ class Solution { public int largestCombination(int[] candidates) { int ans = 0; for (int i = 0; i < 32; ++i) { int t = 0; for (int x : candidates) { t += (x >> i) & 1; } ans = Math.max(ans, t); } return ans; } }
-
class Solution: def largestCombination(self, candidates: List[int]) -> int: ans = 0 for i in range(32): t = 0 for x in candidates: t += (x >> i) & 1 ans = max(ans, t) return ans ############ # 2275. Largest Combination With Bitwise AND Greater Than Zero # https://leetcode.com/problems/largest-combination-with-bitwise-and-greater-than-zero class Solution: def largestCombination(self, candidates: List[int]) -> int: res = 0 for n in range(31, -1, -1): mask = 1 << n curr = 0 for x in candidates: if mask & x > 0: curr += 1 res = max(res, curr) return res
-
function largestCombination(candidates: number[]): number { const n = 24; let ans = 0; for (let i = 0; i < n; i++) { let count = 0; for (let num of candidates) { if ((num >> i) & 1) count++; } ans = Math.max(ans, count); } return ans; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).