Steps to Reduce a Number to Zero

Q: Jaka jest złożoność czasowa redukowania liczby do zera?

Wykonanie procesu zajmuje czas O(log n) , ponieważ co najmniej co drugi krok zmniejsza liczbę o połowę: 61 kroków dla n = 2^31 - 1 . Liczenie cyfr binarnych za pomocą wbudowanych instrukcji bitowych zajmuje O(1) .

Q: Która liczba mniejsza od 2^31 wymaga najwięcej kroków?

2^31 - 1 , czyli liczba zapisana w systemie binarnym jako trzydzieści jeden jedynek. Wymaga 31 odejmowań i 30 połowień, łącznie 61 kroków. Żadna mniejsza liczba nie ma jednocześnie tylu cyfr i tylu jedynek.

PoczątkującyOperacje na bitach Matematyka i symulacja

+10

Zacznij od nieujemnej liczby całkowitej n i powtarzaj jedną regułę, aż osiągnie 0: jeśli liczba jest parzysta, podziel ją przez 2; jeśli jest nieparzysta, odejmij 1. Każde zastosowanie reguły to jeden krok. Zwróć liczbę kroków.

Funkcja

numberOfSteps(n: integer) → integer

ninteger: liczba początkowa
Zwracainteger: liczba kroków, zanim liczba osiągnie 0

Ograniczenia

0 ≤ n ≤ 2³¹ - 1

Przykłady

Wejście: n = 14
Wyjście: 6
Wyjaśnienie: Liczba zmienia się tak: 14 → 7 → 6 → 3 → 2 → 1 → 0: trzy dzielenia przez dwa i trzy odejmowania, 6 kroków.

Wejście: n = 8
Wyjście: 4
Wyjaśnienie: 8 → 4 → 2 → 1 → 0. Potęga dwójki jest dzielona na pół trzy razy i wymaga jednego odejmowania na końcu, czyli 4 kroki.

Wejście: n = 123
Wyjście: 12
Wyjaśnienie: 123 w systemie binarnym to 1111011: siedem cyfr i sześć jedynek. Sześć jedynek wymaga sześciu odejmowań, a sześć cyfr poniżej wiodącej jedynki — sześciu dzieleń przez dwa, czyli 12 kroków.

Pytanie dodatkowe

Załóżmy, że liczbę nieparzystą można również zwiększyć o 1. Jaka jest najmniejsza liczba kroków potrzebna do osiągnięcia 0 i która opcja jest właściwa dla 15?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

W systemie binarnym dzielenie przez dwa usuwa ostatnią cyfrę, a odjęcie 1 od liczby nieparzystej zamienia jej ostatnie 1 na 0. Zatem dla n > 0 odpowiedzią jest liczba cyfr binarnych plus liczba jedynek minus jeden. Bezpośrednie wykonywanie tej reguły również jest szybkie: najwyżej 61 kroków.

Uruchom proces

Intuicja

Wykonaj regułę i policz kroki. Dla 14 pętla odwiedza 7, 6, 3, 2, 1 i 0: sześć kroków.

Odejmowanie zawsze zmienia liczbę nieparzystą w parzystą, więc co najmniej co drugi krok jest dzieleniem przez dwa. Liczba mniejsza niż 2^31 jest dzielona przez dwa najwyżej 30 razy, zanim osiągnie 1. Przy jednym odejmowaniu przed każdym dzieleniem przez dwa i jednym na końcu pętla wykona najwyżej 61 iteracji. Dla n = 0 pętla w ogóle się nie wykonuje, a odpowiedź wynosi 0.

Algorytm

Ustaw steps na 0.
Dopóki n > 0: jeśli n jest parzyste, ustaw n na n / 2, w przeciwnym razie na n-1.
Za każdym razem dodaj 1 do steps.
Zwróć steps.

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

Policz cyfry binarne

Intuicja

Każdy krok albo usuwa ostatnią cyfrę binarną, albo zamienia końcowe 1 na 0. 14 to 1110: dzielenie przez 2 daje 111, a odejmowanie od 111 daje 110. Każde 1 trzeba usunąć jeden raz, co kosztuje jedno odejmowanie na każde 1. Każdą cyfrę trzeba usunąć, wykonując jedno dzielenie przez 2, z wyjątkiem wiodącej jedynki: gdy zostaje tylko 1, jej odjęcie i tak daje 0. Zatem odpowiedź to length - 1 + ones, a dla 14 wynosi 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust i Swift mają wbudowane operacje zliczania obu wartości (zer wiodących i ustawionych bitów), które na większości procesorów kompilują się do pojedynczych instrukcji. W innych językach odczytuj cyfry za pomocą % 2 w pętli trwającej co najwyżej 31 rund. Najpierw obsłuż n = 0: nie ma ono żadnego bitu 1, który mógłby stanowić podstawę wzoru.

Algorytm

Jeśli n == 0, zwróć 0.
Znajdź length, liczbę cyfr binarnych n.
Znajdź ones, liczbę bitów o wartości 1.
Zwróć 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")

Pułapki i przypadki brzegowe

Pominięcie n = 0 we wzorze bitowym. length - 1 + ones daje -1, a liczba zer wiodących dla 0 może być niezdefiniowana (__builtin_clz(0) w C).
Liczenie dzielenia przez połowę dla wiodącej cyfry. 1 zmienia się w 0 przez odejmowanie, więc 8 = 1000 wymaga 4 - 1 + 1 = 4 kroków, a nie 5.
Zapisywanie n = (n-1) / 2 dla liczby nieparzystej i liczenie jednego kroku. Ta linijka wykonuje dwa kroki, więc dla 14 otrzymujemy 4 zamiast 6.
Wykonywanie pętli, dopóki n > 1. Zatrzymuje się ona przed ostatnim krokiem, który zmienia 1 w 0.

Najczęstsze pytania3

Jaka jest złożoność czasowa redukowania liczby do zera?

Wykonanie procesu zajmuje czas O(log n), ponieważ co najmniej co drugi krok zmniejsza liczbę o połowę: 61 kroków dla n = 2^31 - 1. Liczenie cyfr binarnych za pomocą wbudowanych instrukcji bitowych zajmuje O(1).

Która liczba mniejsza od 2^31 wymaga najwięcej kroków?

2^31 - 1, czyli liczba zapisana w systemie binarnym jako trzydzieści jeden jedynek. Wymaga 31 odejmowań i 30 połowień, łącznie 61 kroków. Żadna mniejsza liczba nie ma jednocześnie tylu cyfr i tylu jedynek.

Dlaczego dzielenie przez dwa jest tym samym co przesunięcie w prawo?

Liczba binarna jest sumą potęg liczby dwa. Dzielenie liczby parzystej przez 2 zmniejsza każdą potęgę o jeden, co przesuwa każdą cyfrę o jedno miejsce w prawo i usuwa końcowe 0. To właśnie robi n >> 1, więc dzielenie przez dwa możesz zapisać na oba sposoby.

def numberOfSteps(n):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

n = 14

Oczekiwany wynik