Найдите размер наибольшего подмножества с положительным побитовым И

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти наибольший размер подмножества массива arr[] с положительным побитовым И.

Примечание. Если существует более одного такого подмножества, возвращайте размер только одного подмножества.

Примеры:

Input: arr[] = [7, 13, 8, 2, 3]
Output: 3
Explanation:
The subsets having Bitwise AND positive are {7,13,3} and {7,2,3}  are of length 3, which is of maximum length among all possible subsets.

Input: arr[] = [1, 2, 4, 8]
Output: 1

Подход: данная проблема может быть решена путем подсчета количества установленных битов в каждой соответствующей битовой позиции для всех элементов массива, а затем подсчет максимального количества установленных битов в любой позиции является максимальным количеством требуемого подмножества, потому что побитовое И всех эти элементы всегда положительны.

Иллюстрация:

7 -->  00111
13 --> 01101
 8 --> 01000
 2 --> 00010
 3 --> 00011
       ------
       02233 <-- Evident BitWise AND bit(Most number of 1"s in bit grid)

From above it is clearly evident that we can have maximum of 3 bitwise combinations 
where combinations are listed below as follows:         
{7,13,3}
{7,2,3}

• Инициализируйте массив, скажем, bit[] размером 32 , в котором хранится количество установленных битов в каждой позиции i-го бита.
• Пройдите по заданному массиву и для каждого элемента, скажем, arr[i] увеличьте частоту i-го бита в массиве bit[] , если i-й бит установлен в arr[i] .
• После вышеуказанных шагов выведите максимум массива bit[] , чтобы вывести максимальный размер подмножества.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)

• [(32)* (длина массива), где 32 — постоянное время, поэтому согласно рекуррентному дереву временная сложность имеет порядок N

Вспомогательное пространство: O(1)