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.
  • Also, for nums = [7], the bitwise AND is 7.

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:

1
2
3
4
5
6
7

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:

1
2
3
4

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) where n is the number of elements in the list.
    • Each subset AND calculation takes O(n).
  • 🧺 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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:

  1. Initialize an array of size 32 (to handle up to 32-bit integers) to keep a count of 1s at each bit position.
  2. 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 1 encountered.
  3. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 n numbers, the total time complexity is O(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:

  1. Initialize a variable to keep track of the answer.
  2. Iterate through each bit position from 0 to 31.
  3. For each bit position, count how many numbers have a 1 in this position using the bitwise AND (&) operator.
  4. Update the answer with the maximum count found across all bit positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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;
    }
}
1
2
3
4
5
6
7
8
9

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)