Минимальный размер набора, имеющего либо элемент в диапазоне [0, X], либо нечетную степень 2 с суммой N

Даны два положительных целых числа N и X , задача состоит в том, чтобы найти размер наименьшего набора целых чисел, такого, что сумма всех элементов набора равна N и каждый элемент набора находится либо в диапазоне [0, X] , либо нечетная степень числа 2. Если такого размера множества найти не удается, то выведите «-1» .

Примеры:

Input: N = 11, X = 2
Output: 3
Explanation: The set {1, 2, 8} is the set of minimum number of elements such that the sum of elements is 11 and each element is either in range [0, 2] (i.e, 1 and 2) or is an odd power of 2 (i.e., 8 = 2³).

Input: N = 3, X = 0
Output: -1
Explanation : No valid set exist.

Подход: Данная проблема может быть решена с помощью следующих шагов:

• Поддерживайте размер переменной, в которой хранится минимально возможный размер допустимого набора, и инициализируйте его значением 0 .
• Повторяйте до тех пор, пока значение N не станет больше, чем X , и выполните следующие шаги:
  • Вычтите наибольшую нечетную степень i числа 2 , которая меньше или равна N , из N .
  • Увеличьте значение size на 1 .
• Если значение N положительное, то увеличьте значение размера на 1 .
• После выполнения вышеуказанных шагов выведите значение size в качестве требуемого результата.

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

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