Количество подмножеств с максимально возможным значением XOR

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

Примеры:

Input: arr[] = {3, 1}
Output: 1
Explanation: The maximum possible bitwise XOR of a subset is 3. 
In arr[] there is only one subset with bitwise XOR as 3 which is {3}.
Therefore, 1 is the answer. 

Input: arr[] = {3, 2, 1, 5}
Output: 2

Подход: Эту проблему можно решить с помощью Bit Masking . Выполните следующие шаги, чтобы решить данную проблему.

• Инициализируйте переменную, скажем, maxXorVal = 0 , чтобы сохранить максимально возможное побитовое XOR подмножества в arr[].
• Пройдите по массиву arr[] , чтобы найти значение maxXorVal .
• Инициализируйте переменную, скажем, countSubsets = 0 , чтобы подсчитать количество подмножеств с максимальным побитовым XOR.
• После этого посчитайте количество подмножеств со значением maxXorVal.
• Верните countSubsets в качестве окончательного ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(2 ^·16 )
Вспомогательное пространство : O(1)