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.
Examples
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.
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Naive
Here is the naive approach:
- Generate all possible subsets of the list.
- Calculate the bitwise AND for each subset.
- Track the maximum size of subsets where bitwise AND is greater than 0.
Complexity
- ⏰ Time complexity:
O(n * 2^n)- Generating all subsets takes
O(2^n)wherenis the number of elements in the list. - Each subset AND calculation takes
O(n).
- Generating all subsets takes
- 🧺 Space complexity:
O(n), for storing combinations.
Method 2 - Count max number of bit set at 1 position
To solve this problem, we leverage the bit representation of each number in the array. The intuition is to count the number of 1s in the bit representation of each element. By doing so, the highest count of 1s at any given bit position across the entire array gives us the answer. This might seem challenging, but it becomes much clearer when we visualize the bitwise representation and count the 1s for each bit position.
Bit Pos --> 6 5 4 3 2 1 0
---------------------------------
16 = 0 0 1 0 0 0 0
17 = 0 0 1 0 0 0 1
71 = 1 0 0 0 1 1 1
62 = 0 1 1 1 1 1 0
12 = 0 0 0 1 1 0 0
24 = 0 0 1 1 0 0 0
14 = 0 0 0 1 1 1 0
---------------------------------
Count --> 1 1 4 4 4 3 2
Since the highest number of set bits at a position is 4, we pick 4 as our answer.
Here is the approach:
- Initialize an array of size 32 (to handle up to 32-bit integers) to keep a count of
1s at each bit position. - For each number in the given array:
- Traverse from the least significant to the most significant bit.
- Update the count in the bits array for each
1encountered.
- After processing all numbers, find the maximum count from the bits array, which represents the largest combination size where the bitwise AND is greater than 0.
To count the bit set, we can either use modulo (%) operator or & operator:
Both methods check the least significant bit (LSB):
- Using
num % 2 == 1: If the remainder when divided by 2 is 1, the LSB is set. - Using
num & 1 == 1: If the bitwise AND with 1 is 1, the LSB is set.
Code
Java
class Solution {
public int largestCombination(int[] candidates) {
int[] bits = new int[32];
for (int num : candidates) {
int idx = 0;
while (num > 0) {
bits[idx] += (num & 1);
num >>= 1;
idx++;
}
}
int ans = 0;
for (int count : bits) {
ans = Math.max(ans, count);
}
return ans;
}
}
Using Modulo and division
class Solution {
public int largestCombination(int[] candidates) {
int[] bits = new int[32];
for (int num : candidates) {
int idx = 0;
while (num > 0) {
bits[idx] += num % 2;
num /= 2;
idx++;
}
}
int ans = 0;
for (int count : bits) {
ans = Math.max(ans, count);
}
return ans;
}
}
Using stream
We can also use Arrays.stream() return max count of bit set:
class Solution {
public int largestCombination(int[] candidates) {
int[] bits = new int[32];
for (int num : candidates) {
int idx = 0;
while (num > 0) {
bits[idx] += num % 2;
num /= 2;
idx++;
}
}
return Arrays.stream(bits).max().getAsInt();
}
}
Python
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
bits = [0] * 32
for num in candidates:
idx = 0
while num > 0:
bits[idx] += num % 2
num //= 2
idx += 1
ans = max(bits)
return ans
Complexity
- ⏰ Time complexity:
O(n)- For each number in the array, it takes up to 32 operations to shift through all bits (since we’re dealing with up to 32-bit integers).
- Since there are
nnumbers, the total time complexity isO(n * 32).
- 🧺 Space complexity:
O(1)- We are using a fixed-size array of length 32 to store the count of set bits for each bit position. Other variables used occupy constant space.
- Thus, the space complexity is
O(1).
Method 3 - Count the bits using bitmask
This optimized approach counts the number of 1s at each bit position in all the elements of the given array. The intuition is to loop through all 32 bit positions and count how many numbers have a 1 in the current bit position. The highest count of 1s for any bit position across all numbers will be the answer.
Here is the approach:
- Initialize a variable to keep track of the answer.
- Iterate through each bit position from 0 to 31.
- For each bit position, count how many numbers have a
1in this position using the bitwise AND (&) operator. - Update the answer with the maximum count found across all bit positions.
Code
Java
class Solution {
public int largestCombination(int[] candidates) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int num : candidates) {
if ((num & (1 << i)) != 0) {
count++;
}
}
ans = Math.max(ans, count);
}
return ans;
}
}
Python
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
ans = 0
for i in range(32):
count = sum((num & (1 << i)) != 0 for num in candidates)
ans = max(ans, count)
return ans
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(1)