Разбить число N на нечетные степени 2

Дано положительное целое число N . Задача состоит в том, чтобы напечатать массив в порядке убывания, в котором числа являются нечетными степенями 2 и сумма всех чисел в массиве равна N и размер массива должен быть минимальным, если нет возможности сформировать массив, то печать -1.

Примеры:

 Input: 18
 Output: 8 8 2
 Explanation: Array with sum 18 and which consists 
minimum numbers with odd powers of 2 are [8 8 2] .
Since 8+8+2=19 and 2¹=2, 2³=8 where 1, 3 are odd numbers.

 Input: 7 
Output: -1
Explanation: Since there is no array with sum equal to 7.

Подход: Чтобы решить проблему, следуйте следующей идее:

The idea is to create a  binary array of size (32) and check the set bit position.If  the bit position is odd, store the power of position else store power of (position-1).

Выполните следующие шаги, чтобы решить проблему:

• Создайте двоичный массив максимального размера 32, в котором будет храниться двоичный код числа.
• Если число нечетное, выведите -1 .
• Если число четное, пройдите по двоичному массиву с обратной стороны и проверьте, равен ли бит 1, а позиция бита нечетна, затем возьмите его степень 2 и сохраните его в массиве ответов .
• Если бит равен 1, а позиция бита четная, возьмите 2 экземпляра 2 ^ (позиция-1).
• Если бит равен 0, продолжайте обход двоичного массива.
• Распечатать массив ответов

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

Временная сложность: O(N*log N), где в худшем случае N равно 32.
Вспомогательное пространство: O(N), где N равно 32.