Steps to Reduce a Number to Zero

Q: Độ phức tạp thời gian khi giảm một số về 0 là bao nhiêu?

Quá trình chạy mất thời gian O(log n) , vì ít nhất cứ sau mỗi bước thứ hai, số lượng lại giảm một nửa: 61 bước với n = 2^31 - 1 . Đếm các chữ số nhị phân bằng lệnh bit tích hợp sẵn có độ phức tạp O(1) .

Q: Số nào dưới 2^31 cần nhiều bước nhất?

2^31 - 1 , tức là số có ba mươi mốt chữ số 1 trong hệ nhị phân. Cần 31 phép trừ và 30 lần chia đôi, tổng cộng 61 bước. Không có số nhỏ hơn nào vừa có nhiều chữ số vừa có nhiều chữ số 1 như vậy.

Người mớiThao tác bit Toán và mô phỏng

+10

Bắt đầu với một số nguyên không âm n và lặp lại một quy tắc cho đến khi số đó đạt 0: nếu số đó chẵn, hãy chia số đó cho 2; nếu số đó lẻ, hãy trừ đi 1. Mỗi lần áp dụng quy tắc là một bước. Hãy trả về số bước cần thực hiện.

Hàm

numberOfSteps(n: integer) → integer

ninteger: số bắt đầu
Trả vềinteger: số bước cho đến khi số đó đạt 0

Ràng buộc

0 ≤ n ≤ 2³¹ - 1

Ví dụ

Đầu vào: n = 14
Đầu ra: 6
Giải thích: Số đó lần lượt là 14 → 7 → 6 → 3 → 2 → 1 → 0: ba lần chia đôi và ba lần trừ, 6 bước.

Đầu vào: n = 8
Đầu ra: 4
Giải thích: 8 → 4 → 2 → 1 → 0. Lũy thừa của hai giảm đi một nửa ba lần và cần một phép trừ ở cuối, tổng cộng 4 bước.

Đầu vào: n = 123
Đầu ra: 12
Giải thích: 123 trong hệ nhị phân là 1111011: có bảy chữ số và sáu chữ số 1. Sáu chữ số 1 cần sáu phép trừ, còn sáu chữ số nằm sau chữ số 1 đầu tiên cần sáu lần chia đôi, tổng cộng 12 bước.

Câu hỏi mở rộng

Giả sử số lẻ cũng có thể tăng thêm 1. Cần ít nhất bao nhiêu bước để về 0, và lựa chọn nào đúng với 15?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Trong hệ nhị phân, chia đôi sẽ bỏ chữ số cuối cùng, còn trừ 1 khỏi một số lẻ sẽ biến chữ số 1 cuối cùng thành 0. Vì vậy, với n > 0, đáp án là số chữ số nhị phân cộng với số chữ số 1, rồi trừ đi một. Chạy trực tiếp quy tắc này cũng nhanh: nhiều nhất 61 bước.

Chạy quy trình

Ý tưởng

Chạy quy tắc và đếm số bước. Với 14, vòng lặp đi qua 7, 6, 3, 2, 1 và 0: sáu bước.

Phép trừ luôn biến một số lẻ thành số chẵn, nên cứ nhiều nhất hai bước thì có một lần chia đôi. Một số nhỏ hơn 2^31 được chia đôi nhiều nhất 30 lần trước khi đạt đến 1. Với một phép trừ trước mỗi lần chia đôi và một phép trừ ở cuối, vòng lặp chạy nhiều nhất 61 lần. Với n = 0, vòng lặp không chạy lần nào và đáp án là 0.

Thuật toán

Đặt steps thành 0.
Khi n > 0: nếu n là số chẵn, đặt n thành n / 2, nếu không thì đặt thành n-1.
Mỗi lần, cộng 1 vào steps.
Trả về steps.

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

Đếm các chữ số nhị phân

Ý tưởng

Mỗi bước sẽ bỏ chữ số nhị phân cuối cùng hoặc đổi chữ số 1 ở cuối thành 0. 14 là 1110: chia đôi được 111, rồi trừ khỏi 111 được 110. Mỗi chữ số 1 phải được xóa một lần, tức là mỗi chữ số 1 cần một phép trừ. Mỗi chữ số đều phải được bỏ đi bằng một lần chia đôi, ngoại trừ chữ số 1 đứng đầu: khi chỉ còn 1, phép trừ đó đã cho kết quả 0. Vậy đáp án là length - 1 + ones, và với 14 thì kết quả là 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust và Swift có các hàm dựng sẵn để đếm cả số bit 0 ở đầu lẫn các bit được đặt, và chúng được biên dịch thành một lệnh duy nhất trên hầu hết bộ xử lý. Các ngôn ngữ khác đọc từng chữ số bằng % 2 trong vòng lặp tối đa 31 lần. Xử lý n = 0 trước: giá trị này không có bit 1 nào để làm cơ sở cho công thức.

Thuật toán

Nếu n == 0, trả về 0.
Tìm length, số chữ số nhị phân của n.
Tìm ones, số bit 1.
Trả về 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")

Lỗi thường gặp và trường hợp biên

Quên n = 0 trong công thức bit. length - 1 + ones cho kết quả -1, còn số lượng số 0 ở đầu có thể không xác định khi giá trị là 0 (__builtin_clz(0) trong C).
Tính một lần chia đôi cho chữ số đầu tiên. Phép trừ biến 1 thành 0, vì vậy 8 = 1000 cần 4 - 1 + 1 = 4 bước, không phải 5.
Viết n = (n-1) / 2 cho số lẻ rồi tính một bước. Dòng đó thực hiện hai bước, nên kết quả của 14 là 4 thay vì 6.
Lặp khi n > 1. Cách này dừng trước bước cuối cùng, bước biến 1 thành 0.

Câu hỏi thường gặp3

Độ phức tạp thời gian khi giảm một số về 0 là bao nhiêu?

Quá trình chạy mất thời gian O(log n), vì ít nhất cứ sau mỗi bước thứ hai, số lượng lại giảm một nửa: 61 bước với n = 2^31 - 1. Đếm các chữ số nhị phân bằng lệnh bit tích hợp sẵn có độ phức tạp O(1).

Số nào dưới 2^31 cần nhiều bước nhất?

2^31 - 1, tức là số có ba mươi mốt chữ số 1 trong hệ nhị phân. Cần 31 phép trừ và 30 lần chia đôi, tổng cộng 61 bước. Không có số nhỏ hơn nào vừa có nhiều chữ số vừa có nhiều chữ số 1 như vậy.

Tại sao phép chia đôi tương đương với phép dịch phải?

Số nhị phân là tổng của các lũy thừa của hai. Chia một số chẵn cho 2 làm giảm mỗi lũy thừa đi một, khiến mỗi chữ số dịch sang phải một vị trí và bỏ chữ số 0 cuối cùng. Đó là điều n >> 1 thực hiện, vì vậy bạn có thể viết phép chia đôi theo cả hai cách.

def numberOfSteps(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 14

Đầu ra mong đợi