Минимум операций, необходимых для того, чтобы сделать N четным путем изменения префикса любой длины

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

Примеры:

Input: N = 376502
Output: 0
Explanation: 
– N is already divisible by 2, hence it is an even number so the total number of prefix swaps will be 0.

Input: N = 36543
Output: 2
Explanation: 
– N is not an even number so to make it even first swap the prefix of length 2. Now N=63543
– Now swap the prefix of length 5 and N=34536.

Подход:

Может быть 2 случая.

• N is an even number
• N is an odd number.

В настоящее время,

• Если N — четное число, минимальное количество шагов, чтобы сделать N четным числом, будет равно 0.
• Если N нечетное число, может быть 3 случая.
  1. N не содержит четных цифр. В этом случае невозможно сделать N четным числом, поэтому ответ будет -1.
  2. N содержит четные цифры, и первая цифра N четная. В этом случае мы можем поменять местами целое число, поэтому минимальное количество шагов, чтобы сделать N четным числом, будет равно 1.
  3. N содержит четные цифры, а первая цифра N нечетная. В этом случае мы можем сначала заменить префикс на любую четную цифру, а затем поменять местами все число, поэтому минимальное количество шагов, чтобы сделать N четным числом, будет равно 2.

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

• Инициализируйте строку s[] как строковое представление N.
• Инициализируйте переменную ans как -1 и len как длину строки s[].
• Если (s[len-1] – '0')%2==0 , то значение ans устанавливается равным 0.
• В противном случае выполните следующие задачи:
  • Если первый символ строки s[] четный , тогда ans устанавливается равным 1.
  • Перебрать диапазон [0, len), используя переменную i , и выполнить следующие задачи:
    • Если s[i] четно, то установить ans равным 2 и разбить.
• После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

Временная сложность: O(len), где len — длина строки.
Вспомогательное пространство: O(len)