Сгенерировать массив, среднее значение которого и побитовое ИЛИ побитового XOR равны

Дано целое число N (N нечетно). задача состоит в том, чтобы построить массив arr[] размера N куда 1 ≤ arr[i] ≤ N такое, что побитовое ИЛИ побитового XOR каждой последовательной пары должно быть равно среднему значению построенного arr[]. Формально:

(arr[0] ^ arr[1]) | (arr[2] ^ arr[3] ) | (arr[4] ^ arr[5]) . . . (arr[N-3] ^ arr[N-2] ) |  arr[N-1] = ( arr[0] + arr[1] + arr[2] . . . +a[N-1]) / N

where ^ is the bitwise Xor and | is the bitwise Or.

Примечание. Если возможных массивов несколько, выведите любой из них.

Примеры:

Input: N = 1
Output: arr[] = {1}
Explanation:- Since n=1 hence an=1 and the average of these numbers is also 1.

Input: n = 5
Output: arr[] = {1, 2, 4, 5, 3}
Explanation: (1^2) | (4^5) | 3 = 3 and (1+2+3+4+5)/5 = 3. Hence it forms a valid integer array.

Подход: Реализуйте идею ниже, чтобы решить проблему:

XOR of two same values gives you 0. OR operation with a number will give you the same number. So, if we assign all values to X, then all the XOR values will be 0 except for the last element which does not form any pair. So the Xor will be X. Also the average will become N*X/N = X.

Для реализации идеи выполните следующие шаги:

• Инициализируйте массив размера N.
• Присвойте каждому элементу массива любое значение X (где X находится в диапазоне [1, N]).

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

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