Задача с собеседования в eBay

Дано целое положительное число n. Каждой цифре n присваивается знак в соответствии со следующими правилами:
- самой старшей цифре присваивается положительный знак;
- каждая следующая цифра имеет знак, противоположный знаку предыдущей цифры.
Верните сумму всех цифр с соответствующими знаками.

Пример 1:
Input: n = 521
Output: 4
Объяснение: (+5) + (-2) + (+1) = 4.

Пример 2:
Input: n = 111
Output: 1
Объяснение: (+1) + (-1) + (+1) = 1.

Пример 3:
Input: n = 886996
Output: 0
Объяснение: (+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0.

Ограничения:
1 <= n <= 10⁹

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Сначала разберём базовое решение:
Заводим переменные:
sign - знак текущей цифры, сначала равняется 1 (самая старшая цифра имеет положительный знак)
res - для накопления суммы цифр
Преобразуем n в строку, проходим по ней слева направо:
- присваиваем знак текущей цифре, умножая её на sign, и прибавляем к res;
- меняем sign на противоположный, умножая на -1.

Теперь оптимизируем решение, используя только математические операции без строки:
В цикле проходим по цифрам числа, от младших разрядов к старшим:
- остатком от деления получаем последнюю цифру. Обновляем сумму, вычитая из цифры предыдущий результат.
- переходим к следующему разряду, применяя целочисленное деление.
Формула гарантирует правильное присвоение знаков, так как вычитание предыдущего результата эквивалентно умножению всех накопленных цифр на -1.
К примеру, для n = 521:
res = 1 - 0 = 1
res = 2 - 1 = 1
res = 5 - (2 - 1) = 4
=> +5 - 2 + 1 = 4

Сложность
Базовое:
O(log n) - по времени (количество цифр в числе)
O(log n) - по памяти (храним строку)

Оптимизированное:
O(log n) - по времени
O(1) - по памяти (храним res)

Код
Базовое:
class Solution:
def alternateDigitSum(self, n: int) -> int:
n_str = str(n)
sign = 1
res = 0

for char in n_str:
res = res + int(char) * sign
sign *= -1
return res

Оптимизированное:
class Solution:
def alternateDigitSum(self, n: int) -> int:
res = 0

while n:
res = n % 10 - res
n //= 10
return res

@algoses