Сгенерируйте пары в диапазоне [0, N-1] с суммой побитового И всех пар K

Для данного целого числа N (которое всегда является степенью двойки), обозначающего длину массива, содержащего целые числа в диапазоне [0, N-1] ровно один раз, задача состоит в том, чтобы соединить эти элементы таким образом, чтобы сумма И пары равно K. т.е. ∑ (a _i & b _i ) = K.

Примечание. Каждый элемент может быть частью только одной пары.

Примеры:

Input: N = 4, K = 2
Output: [[0, 1], [2, 3]]
Explanation: Here N = 4 means array contains arr[] = {0, 1, 2, 3}, 
Pairs = [0, 1] and [2, 3]
(0 & 1) + (2 & 3) = 0 + 2 = 2.

Input: N = 8, K = 4
Output: [[4, 7], [1, 6], [2, 5], [0, 3]]

Подход: Решение задачи основано на следующем наблюдении:

There can be four cases as shown below:

• Case 1 (If K = 0):
  • Because N is power of 2, the pairs of form {0+i, N-1-i} will always have bitwise AND as 0 [where i = 0 to (N-1)/2].
  • Here AND of every pair is going to be 0 which implies the sum of every AND pair is going to be 0.
  • After that for K = 0 form these pairs in the following form: [[0, N-1], [1, N-2] . . .].
• Case 2 (If K > 0 and K < N-1):
  • Bitwise AND of K with N-1 is always K.
  • From the above pairs,  exchanging only elements of two pairs and make pairs [K, N-1] and [0, the one which was a pair of K]. So the AND will be K.
• Case 3 (If K = N-1 and N = 4): 
  • In this case pairing is not possible print -1.
• Case 4 (If K = N-1 and N > 4):
  • The maximum AND of any pair can be N-2 which can be formed by N-1 and N-2. So other two pairs can be formed to have bitwise AND =1 i.e. (N-3 with 1) and (0 with 2) because N-3 and 1 are always odd. The other pairs can be kept as it was in case-1. So total bitwise AND sum will be N-1.

Выполните шаги, указанные ниже:

• Проверьте значения K и N.
• Сформируйте пары, как в случае, упомянутом выше, в соответствии со значениями N и K.

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

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