Steps to Reduce a Number to Zero

Q: Berapa kompleksitas waktu untuk mengurangi suatu angka hingga menjadi nol?

Menjalankan proses ini membutuhkan waktu O(log n) , karena setidaknya setiap langkah kedua membagi jumlahnya menjadi dua: 61 langkah untuk n = 2^31 - 1 . Menghitung digit biner dengan instruksi bit bawaan membutuhkan waktu O(1) .

Q: Bilangan mana yang kurang dari 2^31 membutuhkan langkah paling banyak?

2^31 - 1 , yang dalam biner terdiri dari tiga puluh satu angka 1. Bilangan ini memerlukan 31 pengurangan dan 30 pembagian dua, total 61 langkah. Tidak ada bilangan yang lebih kecil yang memiliki digit sebanyak itu sekaligus angka 1 sebanyak itu.

PemulaManipulasi bit Matematika dan simulasi

+10

Mulai dari bilangan bulat nonnegatif n dan ulangi satu aturan sampai mencapai 0: jika bilangannya genap, bagi dengan 2; jika ganjil, kurangi 1. Setiap penerapan aturan dihitung sebagai satu langkah. Kembalikan jumlah langkah yang diperlukan.

Fungsi

numberOfSteps(n: integer) → integer

ninteger: angka awal
Mengembalikaninteger: jumlah langkah hingga angkanya mencapai 0

Batasan

0 ≤ n ≤ 2³¹ - 1

Contoh

Input: n = 14
Output: 6
Penjelasan: Angkanya menjadi 14 → 7 → 6 → 3 → 2 → 1 → 0: tiga kali dibagi dua dan tiga kali dikurangi, 6 langkah.

Input: n = 8
Output: 4
Penjelasan: 8 → 4 → 2 → 1 → 0. Pangkat dua dibagi dua sebanyak tiga kali dan membutuhkan satu pengurangan di akhir, 4 langkah.

Input: n = 123
Output: 12
Penjelasan: 123 dalam biner adalah 1111011: tujuh digit dan enam angka 1. Enam angka 1 memerlukan enam pengurangan, dan enam digit di bawah angka 1 paling depan memerlukan enam pembagian dua, total 12 langkah.

Pertanyaan lanjutan

Misalkan bilangan ganjil juga dapat ditambah 1. Berapa jumlah langkah paling sedikit untuk mencapai 0, dan pilihan mana yang tepat untuk 15?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Dalam biner, membagi dua menghilangkan digit terakhir, dan mengurangi bilangan ganjil dengan 1 mengubah digit terakhirnya yang berupa 1 menjadi 0. Jadi, untuk n > 0, jawabannya adalah jumlah digit biner ditambah jumlah angka 1, lalu dikurangi satu. Menjalankan aturan secara langsung juga cepat, paling banyak 61 langkah.

Jalankan proses

Intuisi

Jalankan aturan tersebut dan hitung langkahnya. Untuk 14, perulangan mengunjungi 7, 6, 3, 2, 1, dan 0: enam langkah.

Pengurangan selalu membuat bilangan ganjil menjadi genap, jadi setidaknya setiap langkah kedua adalah pembagian dua. Bilangan di bawah 2^31 dibagi dua paling banyak 30 kali sebelum mencapai 1. Dengan satu pengurangan sebelum setiap pembagian dua dan satu pengurangan di akhir, perulangan berjalan paling banyak 61 kali. Untuk n = 0, perulangan tidak pernah berjalan dan jawabannya adalah 0.

Algoritma

Atur steps menjadi 0.
Selama n > 0: jika n genap, atur n menjadi n / 2, jika tidak, menjadi n-1.
Tambahkan 1 ke steps setiap kali.
Kembalikan steps.

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

Hitung digit biner

Intuisi

Setiap langkah menghapus digit biner terakhir atau mengubah 1 terakhir menjadi 0. 14 adalah 1110: membaginya dengan dua menghasilkan 111, lalu menguranginya dari 111 menghasilkan 110. Setiap 1 harus dihapus satu kali, jadi dibutuhkan satu pengurangan untuk setiap 1. Setiap digit harus dihapus, dengan satu pembagian dua untuk masing-masing digit, kecuali digit satu di depan: saat hanya tersisa 1, pengurangannya sudah menghasilkan 0. Jadi jawabannya adalah length - 1 + ones, dan untuk 14 hasilnya 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust, dan Swift memiliki bawaan untuk menghitung keduanya (nol di depan dan bit yang bernilai 1) yang dikompilasi menjadi satu instruksi pada sebagian besar prosesor. Bahasa lain membaca digit menggunakan % 2 dalam perulangan paling banyak 31 putaran. Tangani n = 0 terlebih dahulu: angka ini tidak memiliki bit 1 sebagai dasar rumus.

Algoritma

Jika n == 0, kembalikan 0.
Cari length, jumlah digit biner dari n.
Cari ones, jumlah bit 1.
Kembalikan 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")

Jebakan dan kasus tepi

Lupa memasukkan n = 0 dalam rumus bit. length - 1 + ones menghasilkan -1, dan jumlah nol di depan untuk 0 mungkin tidak terdefinisi (__builtin_clz(0) dalam C).
Menghitung pembagian dua untuk digit pertama. Pengurangan mengubah 1 menjadi 0, jadi 8 = 1000 memerlukan 4 - 1 + 1 = 4 langkah, bukan 5.
Menulis n = (n-1) / 2 untuk bilangan ganjil dan menghitungnya sebagai satu langkah. Baris itu melakukan dua langkah, jadi hasil untuk 14 adalah 4, bukan 6.
Melakukan perulangan selama n > 1. Perulangan itu berhenti sebelum langkah terakhir, yang mengubah 1 menjadi 0.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk mengurangi suatu angka hingga menjadi nol?

Menjalankan proses ini membutuhkan waktu O(log n), karena setidaknya setiap langkah kedua membagi jumlahnya menjadi dua: 61 langkah untuk n = 2^31 - 1. Menghitung digit biner dengan instruksi bit bawaan membutuhkan waktu O(1).

Bilangan mana yang kurang dari 2^31 membutuhkan langkah paling banyak?

2^31 - 1, yang dalam biner terdiri dari tiga puluh satu angka 1. Bilangan ini memerlukan 31 pengurangan dan 30 pembagian dua, total 61 langkah. Tidak ada bilangan yang lebih kecil yang memiliki digit sebanyak itu sekaligus angka 1 sebanyak itu.

Mengapa membagi dua sama dengan menggeser ke kanan?

Bilangan biner adalah jumlah pangkat dua. Membagi bilangan genap dengan 2 menurunkan setiap pangkat satu tingkat, sehingga setiap digit bergeser satu tempat ke kanan dan menghilangkan 0 terakhir. Itulah yang dilakukan n >> 1, jadi kamu bisa menulis operasi pembagian menjadi dua dengan cara mana pun.

def numberOfSteps(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 14

Output yang diharapkan