Найдите первые K символов в N-м члене последовательности Туэ-Морса

Даны два целых числа N и K , задача состоит в том, чтобы напечатать первые K бит N ^-го члена последовательности Туэ-Морса . Последовательность Туэ-Морса является двоичной последовательностью. Он начинается с «0» в качестве первого члена. А затем после следующего члена генерируется замена «0» на «01» и «1» на «10».

Примеры:

Input: N = 3, K = 2
Output: 01
Explanation: The 1st term is “0”.
The 2nd term is obtained by replacing “0” with “01” i.e. 2nd term is “01”.
The 3rd term in the sequence is obtained by replacing “0” with “01” and “1” with “10”.
So the 3rd term becomes “0110”. Hence, the 1st 2 characters of the 3rd term is “01”.

Input: N = 4, K = 7
Output: 0110100

Подход: Основной подход к решению этой проблемы состоит в том, чтобы сгенерировать N ^-й член последовательности и напечатать первые K символов этого термина. Это можно сделать с помощью описанного здесь алгоритма.

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

Эффективный подход: описанный выше подход можно оптимизировать, заметив, что i -й член представляет собой конкатенацию (i-1) ^-го члена и инверсию (i-1) ^-го члена, где инверсия означает изменение полярности всех битов в двоичном целом числе. . Следовательно, x -й член, A _i [x] = A _i-1 [x – 1] , если ( x < 2 ^i-1 ), иначе A _i [x] = !A _i-1 [x – 2 ^i-1 ] . Следовательно, используя это соотношение, можно создать рекурсивную функцию для вычисления значения каждого бита в N ^-м члене.

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

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