Количество массивов размером N с элементами в диапазоне [0, (2^K)-1], имеющими максимальную сумму и побитовое И 0

Учитывая два целых числа N и K , задача состоит в том, чтобы найти количество всех возможных массивов размера N с максимальной суммой и побитовым И всех элементов как 0. Кроме того, элементы должны быть в диапазоне от 0 до 2 ^K -1 .

Примеры:

Input: N = 3,  K = 2
Output: 9
Explanation:  2² – 1 = 3, so elements of  arrays should be between 0 to 3. All possible arrays are- [3, 3, 0],  [1, 2, 3], [3, 0, 3], [0, 3, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] Bitwise AND of all the arrays is 0 & also the sum = 6 is maximum 
Input: N = 2, K = 2
Output: 4
Explanation:  All possible arrays are –  [3, 0], [0, 3], [1, 2], [2, 1]

Подход: Чтобы лучше понять подход, выполните следующие шаги:

• Поскольку максимально возможный элемент равен (2 ^K – 1) , а размер массива равен N , поэтому, если все элементы массива равны максимальному элементу, сумма будет максимальной , т.е. N * (2 ^K – 1) = N * ( 2 ⁰ + 2 ¹ + …………….. + 2 ^{К – 1} ) . Имейте в виду, что в ( ^2K – 1) содержится K битов, и все биты установлены.
• Итак, теперь, чтобы сделать побитовое И всех элементов равным 0, мы должны сбросить каждый бит хотя бы в одном элементе. Кроме того, мы не можем сбросить один и тот же бит более чем в 1 элементе , потому что в этом случае сумма не будет максимальной .
• После сброса каждого бита в одном элементе максимально возможная Сумма = N * ( 2 ⁰ + 2 ¹ + ……… + 2 ^{K – 1} ) – ( 2 ⁰ + 2 ¹ + ………. + 2 ^{K – 1} ) = (N * (2 ^К -1 )) - (2 ^К -1) = (N - 1) * (2 ^К - 1) .
• Теперь цель состоит в том, чтобы найти все способы , с помощью которых мы можем сбросить все K бит хотя бы в одном элементе. Вы можете видеть, что для сброса одного бита у вас есть N опций, т.е. вы можете сбросить его в любом из N элементов. Таким образом, общий путь для сброса K битов будет N ^K . Это наш окончательный ответ.

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

Let N = 3, K = 3
 

• Make all elements of the array equal to 2³ – 1 = 7. The array will be [7, 7, 7]. Take binary representation of all elements : [111, 111, 111].
• Unset each bit in exactly one element. Suppose we unset the 3rd bit of the 1st element and the 1st two bits of the 2nd element. array becomes [110, 001, 111] = [6, 1, 7]. This is one of the valid arrays. You can generate all arrays in such a way.
• The total number of arrays will be 3³ = 27.

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

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