Задача с собеседования в eBay
Задача с собеседования в 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
Откликнуться в Telegram →
⚠️ Никогда не платите «за оформление» или «гарантию трудоустройства» — это признак мошенников. Работа ТРУ не несёт ответственности за содержание вакансии.
