Largest Combination With Bitwise AND Greater Than Zero — LeetCode 2275 Python Solution
MediumBit ManipulationArrayHash TableCounting
- Problem
- #2275
- Pattern
- Bit Manipulation
- Reading time
- 2 min
- Source
- leetcode.com
The 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 to 1 & 5 & 3 = 1.
Example
- 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.
Python solution
Python
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
ans = 0
for i in range(max(candidates).bit_length()):
ans = max(ans, sum(x >> i & 1 for x in candidates))
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log M), where n and M are the length of the array \textit{candidates} and the maximum value in the array, respectively |
| Space | O(1) auxiliary |
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero?
- LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero?
- The Python solution on this page runs in O(n \times \log M), where n and M are the length of the array \textit{candidates} and the maximum value in the array, respectively.
- What is the space complexity of LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero cover?
- LeetCode 2275. Largest Combination With Bitwise AND Greater Than Zero is tagged Bit Manipulation, Array, Hash Table and Counting on LeetCode.