Armstrong Number

Q: Độ phức tạp thời gian khi kiểm tra một số Armstrong là bao nhiêu?

n có khoảng log n chữ số, ở đây nhiều nhất là 10. Tách từng chữ số rồi tra cứu mỗi lũy thừa trong một bảng gồm mười giá trị mất O(log n) thời gian và O(1) bộ nhớ. Tính lại d^k bằng một vòng lặp cho mỗi chữ số sẽ khiến độ phức tạp thành O(log² n) .

Người mớiToán và mô phỏng

+10

Một số nguyên dương là số Armstrong khi nó bằng tổng các chữ số của chính nó, mỗi chữ số được nâng lên lũy thừa bằng số chữ số của số đó. 153 có ba chữ số và 1^3 + 5^3 + 3^3 = 153, nên nó là số Armstrong. Hãy viết một hàm (function) nhận n và trả về true nếu đó là số Armstrong, còn không thì trả về false.

Hàm

isArmstrong(n: integer) → boolean

ninteger: số nguyên dương cần kiểm tra
Trả vềboolean: đúng khi n bằng tổng các chữ số của nó, mỗi chữ số được nâng lên lũy thừa bằng số chữ số

Ràng buộc

1 ≤ n ≤ 10⁹

Ví dụ

Đầu vào: n = 153
Đầu ra: true
Giải thích: 153 có 3 chữ số, vì vậy mỗi chữ số được nâng lên lũy thừa 3: 1 + 125 + 27 = 153. Tổng bằng chính số đó, nên đáp án là true.

Đầu vào: n = 10
Đầu ra: false
Giải thích: 10 có 2 chữ số, nên ta bình phương từng chữ số: 1 + 0 = 1, kết quả không phải là 10. Đáp án là false.

Đầu vào: n = 9474
Đầu ra: true
Giải thích: Với 4 chữ số, số mũ là 4: 6561 + 256 + 2401 + 256 = 9474, chính là số đó, nên đáp án là true.

Câu hỏi mở rộng

Chỉ có 31 số Armstrong nằm trong khoảng từ 1 đến 10^9. Bạn có thể liệt kê tất cả mà không cần kiểm tra từng số trong một tỷ số không?

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

Định nghĩa chính là thuật toán: đếm số chữ số của n, nâng từng chữ số lên lũy thừa đó, cộng các kết quả rồi so sánh với n. Số mũ là số chữ số của n này, không phải luôn là 3, và tổng có thể vượt quá 32 bit: 999999999 cho kết quả 9 × 9^9 = 3486784401.

Đọc các chữ số từ chuỗi

Ý tưởng

Chuỗi thập phân của n cung cấp cho bạn cả hai thứ cần thiết: độ dài của chuỗi là số mũ k, còn các ký tự của chuỗi là các chữ số. Với 9474, bạn cộng 9^4 + 4^4 + 7^4 + 4^4. n là số Armstrong khi và chỉ khi tổng bằng n.

Mỗi phép tính lũy thừa cần k phép nhân, tức là mất k bước cho mỗi chữ số, nên phép kiểm tra có độ phức tạp O(k²), với k xấp xỉ log n: ở đây nhiều nhất là 100 phép nhân.

Thuật toán

Chuyển n thành chuỗi thập phân và gọi độ dài của chuỗi là k.
Đặt total kiểu 64 bit bằng 0.
Với mỗi ký tự, chuyển ký tự đó thành chữ số d rồi cộng d^k vào total, dùng phép nhân số nguyên thay vì gọi hàm lũy thừa số thực.
Trả về kết quả cho biết total có bằng n hay không.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Tách các chữ số và tra cứu lũy thừa của chúng

Ý tưởng

Phép tính số học làm cùng việc mà không cần chuỗi. m % 10 là chữ số cuối cùng của m, còn phép chia nguyên cho 10 loại bỏ chữ số đó, vì vậy chia cho đến khi không còn gì sẽ đếm được các chữ số: 9474 trở thành 947, 94, 9, 0, vậy k = 4.

Chỉ có mười chữ số, nên trước tiên hãy tạo powers[d] = d^k cho d từ 0 đến 9. Khi đó, mỗi chữ số chỉ cần tra cứu một lần thay vì thực hiện k phép nhân: thời gian O(log n) và bộ nhớ O(1).

Mỗi số hạng đều bằng không hoặc dương, nên khi tổng vượt quá n, đáp án là false. Với 999999999, điều đó xảy ra sau ba chữ số, khi tổng bằng 3 × 387420489 = 1162261467.

Thuật toán

Đếm số chữ số của n bằng cách chia một bản sao cho 10 cho đến khi giá trị bằng 0; gọi số đếm là k.
Điền powers[d] = d^k cho mọi chữ số d từ 0 đến 9, bằng số nguyên 64 bit.
Chia một bản sao mới của n cho 10 lần nữa, mỗi bước cộng powers[m % 10] vào total.
Nếu total vượt quá n, trả về false ngay lập tức.
Sau chữ số cuối cùng, trả về kết quả cho biết total có bằng n hay không.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

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

Số mũ cố định là 3. Cách này chấp nhận 153 và 370 nhưng loại 9474 và mọi số có một chữ số lớn hơn 1, vì 7^3 = 343.
Tổng 32 bit. 999999999 có tổng là 3486784401, và với n = 10^9, mục trong bảng 9^10 cũng là số đó. C tràn số và dẫn đến hành vi không xác định, Java và C# quay vòng thành số âm, còn bản dựng Rust ở chế độ gỡ lỗi thì gặp lỗi panic.
Lũy thừa dấu phẩy động. Một số môi trường chạy C trả về 24.999... cho pow(5, 2), và phép ép kiểu sẽ cắt thành 24. Thay vào đó, hãy nhân các số nguyên.
So sánh với giá trị sai. Các vòng lặp qua chữ số chia n cho đến khi còn 0, vì vậy hãy thao tác trên một bản sao.
Ký pháp khoa học trong R. as.character(1e9) là "1e+09", gồm năm ký tự; hãy định dạng bằng sprintf("%.0f", n).

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

Số Armstrong là gì?

Một số Armstrong, còn gọi là số tự mãn, bằng tổng các chữ số của chính nó, mỗi chữ số được nâng lên lũy thừa bằng số chữ số. 9474 là một số như vậy vì 9^4 + 4^4 + 7^4 + 4^4 = 9474. Mọi số có một chữ số đều thỏa mãn, vì d^1 = d.

Có bao nhiêu số Armstrong?

Trong hệ cơ số 10, có đúng 88 số dương bằng tổng lũy thừa các chữ số của chúng, và số lớn nhất có 39 chữ số. Danh sách này là hữu hạn vì một số có k chữ số có giá trị ít nhất là 10^(k-1), trong khi tổng lũy thừa các chữ số của nó nhiều nhất là k × 9^k, và từ 61 chữ số trở đi, tổng đó không thể bắt kịp.

Độ phức tạp thời gian khi kiểm tra một số Armstrong là bao nhiêu?

n có khoảng log n chữ số, ở đây nhiều nhất là 10. Tách từng chữ số rồi tra cứu mỗi lũy thừa trong một bảng gồm mười giá trị mất O(log n) thời gian và O(1) bộ nhớ. Tính lại d^k bằng một vòng lặp cho mỗi chữ số sẽ khiến độ phức tạp thành O(log² n).

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 153

Đầu ra mong đợi

true