Steps to Reduce a Number to Zero

Q: Qual è la complessità temporale per ridurre un numero a zero?

L'esecuzione del processo richiede un tempo O(log n) , perché almeno un passaggio sì e uno no il numero viene dimezzato: 61 passaggi per n = 2^31 - 1 . Contare le cifre binarie con le istruzioni bit integrate richiede O(1) .

Q: Quale numero minore di 2^31 richiede il maggior numero di passaggi?

2^31 - 1 , che in binario è composto da trentuno 1. Richiede 31 sottrazioni e 30 divisioni per due, 61 passaggi in totale. Nessun numero più piccolo ha così tante cifre e così tanti 1 contemporaneamente.

PrincipianteManipolazione dei bit Matematica e simulazione

+10

Parti da un intero non negativo n e ripeti una regola finché non raggiunge 0: se il numero è pari, dividilo per 2; se è dispari, sottrai 1. Ogni applicazione della regola è un passaggio. Restituisci il numero di passaggi necessari.

Funzione

numberOfSteps(n: integer) → integer

ninteger: il numero iniziale
Restituisceinteger: il numero di passaggi finché il numero non raggiunge 0

Vincoli

0 ≤ n ≤ 2³¹ - 1

Esempi

Input: n = 14
Output: 6
Spiegazione: Il numero procede così: 14 → 7 → 6 → 3 → 2 → 1 → 0: tre divisioni per due e tre sottrazioni, 6 passaggi.

Input: n = 8
Output: 4
Spiegazione: 8 → 4 → 2 → 1 → 0. Una potenza di due si dimezza tre volte e richiede una sottrazione alla fine, 4 passaggi.

Input: n = 123
Output: 12
Spiegazione: 123 è 1111011 in binario: sette cifre e sei 1. I sei 1 richiedono sei sottrazioni e le sei cifre sotto l'1 iniziale richiedono sei dimezzamenti, 12 passaggi.

Per approfondire

Supponiamo che anche un numero dispari possa aumentare di 1. Qual è il numero minimo di passaggi per arrivare a 0 e quale scelta è corretta per 15?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

In binario, dimezzare elimina l'ultima cifra e sottrarre 1 da un numero dispari trasforma il suo ultimo 1 in uno 0. Quindi, per n > 0, la risposta è il numero di cifre binarie più il numero di 1, meno uno. Applicare direttamente la regola è altrettanto veloce: al massimo 61 passaggi.

Esegui il processo

Intuizione

Esegui la regola e conta i passaggi. Per 14 il ciclo visita 7, 6, 3, 2, 1 e 0: sei passaggi.

Una sottrazione rende sempre pari un numero dispari, quindi almeno un passaggio ogni due è una divisione per due. Un numero inferiore a 2^31 viene diviso per due al massimo 30 volte prima di raggiungere 1. Con una sottrazione prima di ogni divisione per due e una alla fine, il ciclo viene eseguito al massimo 61 volte. Per n = 0 il ciclo non viene mai eseguito e la risposta è 0.

Algoritmo

Imposta steps su 0.
Mentre n > 0: se n è pari, imposta n su n / 2, altrimenti su n-1.
Aggiungi 1 a steps ogni volta.
Restituisci steps.

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

Conta le cifre binarie

Intuizione

Ogni passaggio elimina l’ultima cifra binaria oppure trasforma un 1 finale in 0. 14 è 1110: dimezzando si ottiene 111, e sottraendo da 111 si ottiene 110. Ogni 1 deve essere eliminato una volta, e questo richiede una sottrazione per ogni 1. Ogni cifra deve essere eliminata, con un dimezzamento ciascuna, tranne quella iniziale: quando rimane solo 1, la sua sottrazione produce già 0. Quindi la risposta è length - 1 + ones, e per 14 è 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust e Swift hanno funzioni integrate per entrambi i conteggi (zeri iniziali e bit impostati), che nella maggior parte dei processori vengono compilate in singole istruzioni. Gli altri linguaggi leggono le cifre usando % 2 in un ciclo di al massimo 31 iterazioni. Gestisci prima n = 0: non ha bit a 1 a cui ancorare la formula.

Algoritmo

Se n == 0, restituisci 0.
Trova length, il numero di cifre binarie di n.
Trova ones, il numero di bit a 1.
Restituisci 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")

Trappole e casi limite

Dimenticare n = 0 nella formula dei bit. length - 1 + ones restituisce -1, e il conteggio degli zeri iniziali può essere indefinito se vale 0 (__builtin_clz(0) in C).
Contare una divisione per due per la cifra iniziale. 1 diventa 0 con una sottrazione, quindi 8 = 1000 richiede 4 - 1 + 1 = 4 passaggi, non 5.
Scrivere n = (n-1) / 2 per un numero dispari e contare un passaggio. Quella riga esegue due passaggi, quindi per 14 si ottiene 4 invece di 6.
Eseguire il ciclo mentre n > 1. Così ci si ferma prima dell'ultimo passaggio, che trasforma 1 in 0.

Domande frequenti3

Qual è la complessità temporale per ridurre un numero a zero?

L'esecuzione del processo richiede un tempo O(log n), perché almeno un passaggio sì e uno no il numero viene dimezzato: 61 passaggi per n = 2^31 - 1. Contare le cifre binarie con le istruzioni bit integrate richiede O(1).

Quale numero minore di 2^31 richiede il maggior numero di passaggi?

2^31 - 1, che in binario è composto da trentuno 1. Richiede 31 sottrazioni e 30 divisioni per due, 61 passaggi in totale. Nessun numero più piccolo ha così tante cifre e così tanti 1 contemporaneamente.

Perché dividere per due equivale a uno spostamento a destra?

Un numero binario è una somma di potenze di due. Dividere un numero pari per 2 riduce di uno ogni potenza, spostando ogni cifra di una posizione a destra e rimuovendo lo 0 finale. È ciò che fa n >> 1, quindi puoi scrivere la divisione a metà in entrambi i modi.

def numberOfSteps(n):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

n = 14

Output atteso