Максимизируйте шаги, чтобы уменьшить N до 0, вычитая любое значение, кроме 1 и N на каждом шаге

Учитывая число N , задача состоит в том, чтобы найти максимальное количество шагов преобразования N в ноль, где на каждом шаге число m ( 1 < m < N (начальное значение N)) вычитается из N . Если невозможно преобразовать N в 0 таким образом, выведите -1 .

Примечание. Значения m могут быть разными на разных этапах.

Примеры:

Input: N = 14
Output: 7
Explanation: The steps are as shown below:
14 – 2 = 12 – 1st Operation
12 – 2 = 10  – 2nd Operation
10 – 2 = 8  – 3rd Operation
8 – 2 = 6  –  4th Operation
6 – 2 = 4  – 5th operation
4 -2 = 2  – 6th Operation
2-2 = 0  – 7th Operation

Input: N = 2
Output: -1
Explanation: Not possible to obtain 0

Input: N = 5
Output: 2
Explanation: Subtract 2 and 3 from 5 respectively

Подход: Проблема может быть решена на основе простого наблюдения. Если N = 1, 2 или 3 , невозможно получить 0 из N . Во всех остальных случаях есть возможный способ. Количество шагов будет максимальным, если на каждом шаге будет вычтено минимальное значение, т.е. 2 . Таким образом, общее количество шагов становится N/2 . (Когда N нечетное, последним вычитаемым значением будет 3, потому что 1 не допускается)

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

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