Количество различных перестановок длины N, имеющих побитовое И как ноль

Для заданного целого числа N. Задача состоит в том, чтобы найти количество различных перестановок длины N , таких, что побитовое И значение каждой перестановки равно нулю .

Примеры:

Input: N = 1
Output: 0 
Explanation: There is only one permutation of length 1: [1] and it’s bitwise AND is 1 . 
 

Input: N = 3 
Output: 6 
Explanation: Permutations of length N having bitwise AND as 0 are : [1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 1, 2], [2, 3, 1], [3, 2, 1] . 

Подход: Задачу можно решить с помощью наблюдений. Можно заметить, что если число является степенью 2 , скажем, « x », побитовое И x & (x-1) всегда равно нулю. Все перестановки длины больше 1 имеют побитовое И как ноль , а для N = 1 количество различных перестановок равно 0 . Следовательно, необходимое количество равно количеству возможных перестановок, т.е. N!

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

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