Steps to Reduce a Number to Zero

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

Wykonanie procesu zajmuje O(log n) , ponieważ co najmniej co drugi krok zmniejsza liczbę o połowę. Dla n = 2^31 - 1 potrzeba 61 kroków. Zliczanie cyfr binarnych za pomocą wbudowanych instrukcji bitowych ma złożoność O(1) .

Q: Jaki jest wzór na liczbę kroków?

Dla n > 0 odpowiedzią jest długość n w systemie binarnym pomniejszona o jeden, plus liczba bitów o wartości 1. Każdy bit o wartości 1 wymaga jednego odejmowania, a każda cyfra poniżej wiodącej jedynki wymaga jednego dzielenia przez dwa. Dla n = 0 odpowiedzią jest 0 .

Q: Która liczba mniejsza niż 2^31 wymaga największej liczby kroków?

2^31 - 1 , czyli trzydzieści jedynek w systemie binarnym. Wymaga 31 odejmowań i 30 dzieleń przez dwa, łą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, które są potrzebne.

Funkcja

numberOfSteps(n: integer) → integer

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

Ograniczenia

0 ≤ n ≤ 2³¹ - 1

Przykłady

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

Wejście: n = 8
Wyjście: 4
Wyjaśnienie: 8 → 4 → 2 → 1 → 0. Potęga dwójki zmniejsza się o połowę trzy razy i na końcu wymaga jednego odejmowania, 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 wymaga sześciu dzieleń przez dwa — łącznie 12 kroków.

+12 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że liczba nieparzysta może również zwiększyć się o 1 zamiast zmniejszyć. Jaka jest najmniejsza liczba kroków potrzebnych do osiągnięcia 0 i który wybór jest właściwy dla 15?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Wykonanie reguły jest już szybkie: każde dzielenie przez dwa zmniejsza liczbę o połowę, więc nawet 2^31 - 1 wymaga tylko 61 kroków. Ciekawe jest to, co reguła robi z cyframi binarnymi. Dzielenie przez dwa usuwa ostatnią cyfrę, a odjęcie 1 od nieparzystej liczby zamienia jej ostatnie 1 na 0. Zatem odpowiedzią jest liczba cyfr plus liczba jedynek minus jeden.

Uruchom proces

Intuicja

Wykonuj to, co mówi instrukcja. Dopóki n jest większe od 0, dziel je przez dwa, jeśli jest parzyste, odejmij 1, jeśli jest nieparzyste, i zlicz krok. Dla 14 pętla odwiedza wartości 7, 6, 3, 2, 1 i 0 — sześć kroków.

Pętla jest krótka, ponieważ odejmowanie zawsze sprawia, że liczba nieparzysta staje się parzysta, więc co najmniej co drugi krok jest dzieleniem przez dwa. Liczba mniejsza od 2^31 zostanie podzielona przez dwa najwyżej 30 razy, zanim osiągnie 1, a przy jednym odejmowaniu przed każdym takim dzieleniem i jednym na końcu pętla wykona najwyżej 61 iteracji.

Wejście 0 nie wymaga specjalnego przypadku: warunek pętli od razu nie jest spełniony, 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

Obserwuj proces w systemie binarnym. 14 to 1110. Dzielenie przez dwa usuwa ostatnią cyfrę: 111. Odjęcie 1 od liczby nieparzystej zeruje jej ostatnią cyfrę, czyli 1: 110. Każdy krok albo usuwa ostatnią cyfrę, albo zamienia końcowe 1 na 0.

Teraz policz. Każde 1 w liczbie musi zostać wyzerowane raz, co kosztuje jedno odejmowanie na każde 1. Każda cyfra musi zostać usunięta, co kosztuje jedno dzielenie przez dwa na każdą cyfrę, z wyjątkiem wiodącej jedynki: gdy zostaje już tylko 1, odejmowanie, które ją zeruje, daje od razu 0. Zatem odpowiedź to length - 1 + ones. Dla 14 = 1110 daje to 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust i Swift mają wbudowane funkcje do obu zliczeń (zliczania wiodących zer i zliczania jedynek), które na większości procesorów kompilują się do pojedynczych instrukcji. W pozostałych językach zapisuje się n w systemie binarnym i zlicza znaki albo odczytuje cyfry za pomocą % 2; jest to pętla wykonująca najwyżej 31 iteracji. Najpierw zwróć 0 dla n = 0: ta liczba nie ma bitu o wartości 1, który byłby podstawą wzoru.

Algorytm

Jeśli n == 0, zwróć 0.
Znajdź length, czyli liczbę cyfr binarnych w n.
Znajdź ones, czyli 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

Reguła składa się z dwóch wierszy. Błędy dotyczą przypadków brzegowych i błędu o jeden w formule.

Pominięcie n = 0 we wzorze na liczbę bitów. Gdy nie ma cyfr ani jedynek, length - 1 + ones daje -1, a liczba początkowych zer może być niezdefiniowana (__builtin_clz(0) w C).
Liczenie dzielenia przez 2 dla początkowej cyfry. 1 zmienia się w 0 przez odejmowanie, więc 8 = 1000 wymaga 4 - 1 + 1 = 4 kroków, a nie 5.
Łączenie dwóch kroków w jeden. Zapisanie n = (n-1) / 2 dla liczby nieparzystej wykonuje jednocześnie odejmowanie i dzielenie przez 2, więc do licznika trzeba dodać 2, a nie 1. W przeciwnym razie dla 14 otrzymamy 4 zamiast 6.
Wykonywanie pętli, dopóki n > 1. Zatrzymuje się ona o jeden krok za wcześnie, ponieważ ostatni krok zmienia 1 w 0. Pętla musi działać aż n osiągnie 0.

Najczęstsze pytania4

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

Wykonanie procesu zajmuje O(log n), ponieważ co najmniej co drugi krok zmniejsza liczbę o połowę. Dla n = 2^31 - 1 potrzeba 61 kroków. Zliczanie cyfr binarnych za pomocą wbudowanych instrukcji bitowych ma złożoność O(1).

Jaki jest wzór na liczbę kroków?

Dla n > 0 odpowiedzią jest długość n w systemie binarnym pomniejszona o jeden, plus liczba bitów o wartości 1. Każdy bit o wartości 1 wymaga jednego odejmowania, a każda cyfra poniżej wiodącej jedynki wymaga jednego dzielenia przez dwa. Dla n = 0 odpowiedzią jest 0.

Która liczba mniejsza niż 2^31 wymaga największej liczby kroków?

2^31 - 1, czyli trzydzieści jedynek w systemie binarnym. Wymaga 31 odejmowań i 30 dzieleń przez dwa, łą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 dwójki. 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. Dokładnie to robi n >> 1, więc dzielenie przez dwa możesz zapisać na oba sposoby.

Python

def numberOfSteps(n):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

n = 14

Oczekiwane