Подсчитайте способы представить N как XOR различных целых чисел, не превышающих N

Учитывая положительное целое число N , задача состоит в том, чтобы найти количество способов представить N как побитовое XOR различных положительных целых чисел, меньших или равных N .

Примеры:

Input: N = 5
Output: 4
Explanation: The given number N(= 5) can be represented as:

1. 5 = 5
2. 5 = (4 ^ 1)
3. 5 = (5 ^ 3 ^ 2 ^ 1)
4. 5 = (4 ^ 3 ^ 2)

Therefore, the total count is 4.

Input: N = 6
Output: 8

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

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

Эффективный подход. Описанный выше подход можно оптимизировать, используя наблюдение, что количество способов представить N как побитовое исключающее ИЛИ различных положительных целых чисел определяется выражением .

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

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