Последний оставшийся элемент после многократного удаления нечетных индексированных элементов

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

Примеры:

Input: N = 4
Output: 4
Explanation: 

Input: N = 9
Output: 8

Наивный подход: Наивный подход к решению вышеуказанной проблемы заключается в сохранении последовательности. Повторите последовательность и удалите из нее элементы с нечетным индексом. Повторяйте вышеуказанные шаги, пока не останется только один элемент.

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

Эффективный подход: рассмотрите следующее наблюдение:

• На первом шаге будут удалены все нечетные элементы с разницей в 2
• На втором шаге будут удалены все четные элементы, начиная с 2, с разницей 4
• На втором шаге будут удалены все четные элементы, начиная с 4, с разницей 8
• Точно так же на следующем шаге будут удалены все элементы с разностью 16 и так далее.
• Таким образом, на каждом шаге вы можете видеть, что элементы с разницей 2 ^X будут удалены.
• При этом в конечном итоге будут удалены все элементы, кроме наибольшей степени двойки, присутствующей в последовательности.

Из приведенных выше наблюдений можно сделать вывод, что:

last remaining element (L) = log₂ N

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

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