Steps to Reduce a Number to Zero

Q: Какова временная сложность сведения числа к нулю?

Выполнение процесса занимает время O(log n) , потому что как минимум каждый второй шаг уменьшает число вдвое. Для n = 2^31 - 1 это 61 шаг. Подсчёт двоичных цифр с помощью встроенных битовых инструкций занимает O(1) .

Q: Какова формула для вычисления количества шагов?

Для n > 0 ответ равен длине n в двоичной системе счисления минус один плюс количество единичных битов. Каждый бит со значением 1 требует одного вычитания, а каждая цифра после старшей единицы — одного деления пополам. Для n = 0 ответ равен 0 .

Q: Какое число меньше 2^31 требует наибольшего количества шагов?

2^31 - 1 , то есть тридцать одна единица в двоичной системе счисления. Для него требуется 31 вычитание и 30 делений пополам — всего 61 шаг. Ни одно меньшее число не имеет одновременно столько же цифр и единиц.

НовичокБитовые операции Математика и моделирование

+10

Начните с неотрицательного целого числа n и повторяйте одно правило, пока не достигнете 0: если число чётное, разделите его на 2; если нечётное, вычтите 1. Каждое применение правила — это один шаг. Верните количество шагов.

Функция

numberOfSteps(n: integer) → integer

ninteger: начальное число
Возвращаетinteger: количество шагов до тех пор, пока число не достигнет 0

Ограничения

0 ≤ n ≤ 2³¹ - 1

Примеры

Ввод: n = 14
Вывод: 6
Пояснение: Число проходит путь 14 → 7 → 6 → 3 → 2 → 1 → 0: три деления пополам и три вычитания, 6 шагов.

Ввод: n = 8
Вывод: 4
Пояснение: 8 → 4 → 2 → 1 → 0. Степень двойки уменьшается вдвое три раза, а в конце требуется одно вычитание — 4 шага.

Ввод: n = 123
Вывод: 12
Пояснение: 123 в двоичной системе — это 1111011: семь цифр и шесть единиц. Шесть единиц требуют шести вычитаний, а шесть цифр после старшей единицы — шести делений пополам, всего 12 шагов.

+12 скрытых тестов при отправке

Дополнительный вопрос

Предположим, нечётное число также можно увеличить на 1 вместо уменьшения. Каково минимальное число шагов, чтобы достичь 0, и какой выбор верен для 15?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Выполнять правило и так быстро: при каждом делении пополам число уменьшается вдвое, поэтому даже для 2^31 - 1 требуется всего 61 шаг. Интересно посмотреть, что это правило делает с двоичными цифрами. При делении пополам последняя цифра отбрасывается, а при вычитании 1 из нечётного числа его последняя 1 превращается в 0. Значит, ответ — это количество цифр плюс количество единиц минус один.

Запустите процесс

Идея

Выполните то, что указано в условии. Пока n больше 0, делите его пополам, если оно чётное, вычитайте 1, если оно нечётное, и считайте шаги. Для 14 цикл проходит через 7, 6, 3, 2, 1 и 0 за шесть шагов.

Цикл короткий, потому что вычитание всегда делает нечётное число чётным, поэтому как минимум каждый второй шаг — это деление пополам. Число меньше 2^31 делится пополам не более 30 раз, прежде чем станет равным 1; учитывая одно вычитание перед каждым делением пополам и одно в конце, цикл выполняется не более 61 раза.

Для входного значения 0 не нужен особый случай: условие цикла сразу не выполняется, и ответ равен 0.

Алгоритм

Установи steps в значение 0.
Пока n > 0: если n чётное, установи n в значение n / 2, иначе — в значение n-1.
Каждый раз прибавляй 1 к steps.
Верни steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

Подсчитайте двоичные цифры

Идея

Посмотри на процесс в двоичной системе. 14 — это 1110. Деление пополам убирает последнюю цифру: 111. Вычитание 1 из нечётного числа обнуляет его последнюю цифру, 1: 110. Таким образом, каждый шаг либо удаляет последнюю цифру, либо превращает последнюю 1 в 0.

Теперь посчитаем. Каждую 1 в числе нужно обнулить один раз, на это требуется одно вычитание для каждой 1. Нужно удалить каждую цифру, на это требуется одно деление пополам для каждой цифры, кроме ведущей: когда остаётся только 1, вычитание, которое обнуляет её, уже даёт 0. Значит, ответ — length - 1 + ones. Для 14 = 1110 это 4 - 1 + 3 = 6.

В Java, C, C++, Go, Rust и Swift есть встроенные функции для обоих подсчётов (подсчёта ведущих нулей и количества единичных битов), которые на большинстве процессоров компилируются в одну инструкцию. В остальных языках записывают n в двоичном виде и подсчитывают символы либо считывают цифры с помощью % 2; это цикл максимум на 31 итерацию. Сначала верни 0 для n = 0: в этом числе нет бита со значением 1, который служил бы опорой для формулы.

Алгоритм

Если n == 0, верни 0.
Найди length — количество двоичных цифр в n.
Найди ones — количество битов, равных 1.
Верни length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Ловушки и крайние случаи

Правило состоит из двух строк. Ошибки возникают на краевых случаях и из-за ошибки на единицу в формуле.

Забывают учесть n = 0 в формуле для битов. Если нет цифр и единиц, length - 1 + ones даёт -1, а количество ведущих нулей для 0 может быть не определено (__builtin_clz(0) в C).
Считают деление пополам для ведущей цифры. 1 превращается в 0 вычитанием, поэтому для 8 = 1000 требуется 4 - 1 + 1 = 4 шага, а не 5.
Объединяют два шага в один. Запись n = (n-1) / 2 для нечётного числа одновременно выполняет вычитание и деление пополам, поэтому к счётчику нужно прибавить 2, а не 1. Иначе для 14 получится 4 вместо 6.
Используют цикл с условием n > 1. Он останавливается на один шаг раньше, потому что на последнем шаге 1 превращается в 0. Цикл должен выполняться, пока n не станет равным 0.

Частые вопросы4

Какова временная сложность сведения числа к нулю?

Выполнение процесса занимает время O(log n), потому что как минимум каждый второй шаг уменьшает число вдвое. Для n = 2^31 - 1 это 61 шаг. Подсчёт двоичных цифр с помощью встроенных битовых инструкций занимает O(1).

Какова формула для вычисления количества шагов?

Для n > 0 ответ равен длине n в двоичной системе счисления минус один плюс количество единичных битов. Каждый бит со значением 1 требует одного вычитания, а каждая цифра после старшей единицы — одного деления пополам. Для n = 0 ответ равен 0.

Какое число меньше 2^31 требует наибольшего количества шагов?

2^31 - 1, то есть тридцать одна единица в двоичной системе счисления. Для него требуется 31 вычитание и 30 делений пополам — всего 61 шаг. Ни одно меньшее число не имеет одновременно столько же цифр и единиц.

Почему деление пополам — это то же самое, что сдвиг вправо?

Двоичное число — это сумма степеней двойки. При делении чётного числа на 2 степень каждой цифры уменьшается на единицу, из-за чего каждая цифра сдвигается на одну позицию вправо, а последняя 0 пропускается. Именно это и делает n >> 1, поэтому деление пополам можно записать любым из этих способов.

Python

def numberOfSteps(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

n = 14

Ожидается