Минимальное количество заданных операций, которое необходимо выполнить, чтобы уменьшить N до 0

Учитывая целое число N , задача состоит в том, чтобы уменьшить N до 0 за минимальное количество операций, используя следующие операции любое количество раз:

• Измените самый правый (0 ^-й ) бит в двоичном представлении N.
• Измените i ^-й бит в двоичном представлении N , если (i-1) ^-й бит установлен в 1, а (i-2) ^-й по 0 ^-й биты установлены в 0.

Примеры:

Input: N = 3
Output: 2
Explanation: The binary representation of 3 is “11”.
“11″ → “01” with the 2nd operation since the 0th bit is 1.
“01″ → “00″ with the 1st operation.

Input: N = 6
Output: 4
Explanation: The binary representation of 6 is “110”.
“110” → “010” with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
“010” → “011” with the 1st operation.
“011” → “001” with the 2nd operation since the 0th bit is 1.
“001” → “000” with the 1st operation.

Подход: Идея основана на следующих наблюдениях:

• 1 → 0 требуется 1 операция.
  2 → 0, т.е. 10 → 11 → 01 → 0 требует 3 операций.
  4 → 0 т.е. 100 → 101 → 111 → 110 → 010 → 11 → 01 → 0 нужно 7 операций.
  Следовательно, его можно обобщить для любой степени двойки, т. е. для 2 ^k требуется 2 ^{(k + 1)} -1 операции.
• Если a → b требует k операции, то b → a также требует k операции.

Промежуточные числа от 2 ⁿ до 2 ^(n-1) содержат все числа от 2 ⁿ до 2 ^(n-1) , что показывает, что любое данное неотрицательное целое число может быть преобразовано в 0. Пусть f(n) — функция, найти минимальное количество необходимых операций. Рекуррентное соотношение:
f(n) = f(2k) – f(n xor ^2k ), где ^k = следующий бит старшего бита n.

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

• Создайте рекурсивную функцию, которая принимает число N в качестве параметра.
  • Если значение N равно 0 , вернуть 0 .
  • В противном случае найдите наивысшую степень числа 2, меньшую или равную N, и сохраните ее в переменной X .
  • Сохраните значение, возвращенное рекурсивным вызовом функции для (X^(X/2)^N) в переменной S .
  • Добавьте значение X к S и верните его.

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

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