Найдите значение X в диапазоне [0, K], которое может максимизировать сумму X XOR по заданному массиву

Учитывая массив a[] размера N и целое число K, задача состоит в том, чтобы найти значение X в диапазоне [0, K], которое может максимизировать значение данной функции.

• Xor-sum(X) = (X XOR A[0]) + (X Xor A[1]) + (X Xor A[2]) + __________+ (X Xor A[N-1]).

Примеры:

Input: a[] = {1, 2, 3, 4, 5, 6}, N=6, K=10
Output: 8
Explanation: The value of X is 1 for which the required sum becomes maximum.

Input: a[] = {1, 6}, N=2, K=7
Output: 0

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

• Инициализируйте переменные max и X как 0 и -1 , чтобы сохранить определенную максимальную сумму и значение X , для которого это происходит.
• Переберите диапазон [0, K], используя переменную j , и выполните следующие задачи:
  • Инициализируйте переменную sum как 0 , чтобы сохранить определенную сумму.
  • Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
    • Установите значение суммы как sum + j^a[i].
  • Если сумма больше, чем max, то установите значение max как сумму , а X как j.
• После выполнения вышеуказанных шагов выведите значение X в качестве ответа.

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

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