Минимальные деления, чтобы уменьшить N до 1, следуя заданным условиям

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

• Выберите два целых числа X и Y так, чтобы X+Y было четным.
• Замените N на N/X ^Y, где X ^Y является делителем N

Примечание. Если уменьшить N до 1 невозможно, то вернуть -1.

Примеры:

Input: N = 35
Output: 1
Explanation: Select X = 35 and Y = 1. X+Y = 36 which is even,  
and X^Y = 35 is a divisor of N = 35 so this is a valid choice.

Input: 44
Output: 2

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

• If N is odd then X can be chosen as X = N and Y = 1. So X^Y = X = N and also X + Y = X + 1 = even.
• If N is even then N can be written as N = 2^p * X where p is any integer and X is an odd number (can be 1). 
  • If p is odd then it is never possible to reduce the number to 1 as 2 + p will always be odd.
  • Otherwise, it will take 2 moves to reduce the number to 1: One step to reduce the number to X and another step to reduce it from X to 1.
  • If X = 1 then no 2nd step is needed and 1 step will be sufficient.

Выполните шаги, указанные ниже, чтобы решить проблему:

• Найдите, является ли число нечетным или четным n.
• Если число четное, то:
  • Если 2 возвести в нечетную степень, то ответ невозможен.
  • В противном случае получите минимальное количество шагов, как показано в приведенном выше наблюдении.
• Если число нечетное, требуется только один шаг.

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

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