Сложность: medium
Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.
Пример:
Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.
Step 5) 4 is even, divide by 2 and obtain 2.
Step 6) 2 is even, divide by 2 and obtain 1.
👨💻 Алгоритм:
1⃣Инициализируйте переменную operations значением 0.
2⃣Повторяйте операции, пока длина строки s больше 1:
Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит.
В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.
3⃣Верните количество операций.
😎 Решение:
class Solution:
def numSteps(self, s: str) -> int:
operations = 0
s = list(s)
while len(s) > 1:
if s[-1] == '0':
s.pop()
else:
i = len(s) - 1
while i >= 0 and s[i] == '1':
s[i] = '0'
i -= 1
if i < 0:
s.insert(0, '1')
else:
s[i] = '1'
operations += 1
return operations
Ставь 👍 и забирай 📚 Базу знаний