Steps to Reduce a Number to Zero

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

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

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 шагов.

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

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

Подсказки

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

Открыто 0 из 3

Решение

В двоичной системе деление пополам отбрасывает последнюю цифру, а вычитание 1 из нечётного числа превращает последнюю 1 в 0. Поэтому для n > 0 ответ равен количеству двоичных цифр плюс количество единиц минус один. Прямое применение правила тоже выполняется быстро: не более 61 шагов.

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

Идея

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

Вычитание всегда превращает нечётное число в чётное, поэтому как минимум каждый второй шаг — это деление пополам. Число меньше 2^31 делится пополам не более 30 раз, прежде чем достигнет 1. Если перед каждым делением пополам выполнить одно вычитание и ещё одно в конце, цикл выполнится не более 61 раза. Для n = 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

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

Идея

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

В Java, C, C++, Go, Rust и Swift есть встроенные функции для подсчёта обоих значений (ведущих нулей и установленных битов), которые на большинстве процессоров компилируются в одну инструкцию. В других языках цифры считываются с помощью % 2 в цикле максимум из 31 итераций. Сначала обработайте случай 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 для нечётного числа и считать это за один шаг. Эта строка выполняет два шага, поэтому для 14 получается 4 вместо 6.
Выполнять цикл, пока n > 1. Он останавливается до последнего шага, который превращает 1 в 0.

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

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

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

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

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

Почему деление пополам равносильно сдвигу вправо?

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

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

Тест #1

Тест #2

Тест #3

Аргумент

n = 14

Ожидаемый вывод