Sum of Digits

Q: Độ phức tạp thời gian của việc tính tổng các chữ số của một số là bao nhiêu?

Mỗi chữ số tương ứng với một bước, nên độ phức tạp là O(d) , trong đó d là số chữ số. Một số n có khoảng log10(n) + 1 chữ số, nên người ta thường viết cùng giới hạn này là O(log n) . Với số nguyên 32 bit, số bước nhiều nhất là 10.

Q: Phiên bản chuỗi hay phiên bản số học tốt hơn?

Cả hai đều có độ phức tạp O(d) và đều đúng. Cách dùng chuỗi ngắn hơn trong nhiều ngôn ngữ nhưng tạo ra một bản sao các chữ số. Cách dùng phép tính số học cần thêm bộ nhớ O(1) và cho thấy bạn hiểu cách % 10 và / 10 tách một số thành từng phần. Kiến thức này sẽ hữu ích với các bài toán về số đối xứng và đảo ngược chữ số.

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

+10

Bạn nhận được một số nguyên không âm n. Hãy trả về tổng các chữ số thập phân của nó. Ví dụ, các chữ số của 482 là 4, 8 và 2, nên đáp án là 14.

Hàm

sumOfDigits(n: integer) → integer

ninteger: số nguyên không âm có các chữ số mà bạn cộng lại
Trả vềinteger: tổng các chữ số thập phân của n

Ràng buộc

0 ≤ n ≤ 2³¹-1

Ví dụ

Đầu vào: n = 9045
Đầu ra: 18
Giải thích: Các chữ số của 9045 là 9, 0, 4 và 5, và 9 + 0 + 4 + 5 = 18. Số 0 không làm tăng tổng nhưng vẫn được tính là một chữ số.

Đầu vào: n = 7
Đầu ra: 7
Giải thích: Số có một chữ số có tổng các chữ số bằng chính nó, nên 7 cho kết quả 7.

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

Tách số đó thành từng chữ số một. Bạn có thể đọc dạng văn bản thập phân của số, hoặc lấy chữ số cuối bằng n % 10 rồi bỏ chữ số đó bằng phép chia nguyên cho 10. Cả hai cách đều cần một bước cho mỗi chữ số, ký hiệu là d, và ở đây d ≤ 10. Cách dùng phép toán không cần thêm bộ nhớ.

Đọc các chữ số dưới dạng văn bản

Ý tưởng

Chuyển n thành văn bản thập phân, để 9045 trở thành các ký tự 9, 0, 4 và 5, rồi cộng giá trị của từng ký tự.

Ký tự chưa phải là số. Ký tự '4' được lưu dưới dạng mã 52, vì vậy bạn cần phân tích ký tự đó hoặc trừ đi mã của '0': '4' - '0' = 4. Các ký tự chữ số có mã liên tiếp nhau, vì vậy phép trừ đó có tác dụng với cả mười chữ số.

Vòng lặp mất thời gian O(d), còn văn bản cần thêm O(d) không gian bộ nhớ.

Thuật toán

Chuyển n thành văn bản thập phân.
Đặt total = 0.
Với mỗi ký tự, cộng giá trị chữ số của nó vào total.
Trả về total.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Bóc chữ số cuối cùng bằng % 10

Ý tưởng

Số dư khi chia cho 10 là chữ số cuối cùng: 9045 % 10 = 5. Phép chia nguyên cho 10 loại bỏ chữ số đó: 9045 / 10 = 904 khi bỏ phần thập phân. Lặp lại cặp phép tính này, ta lấy được các chữ số từ phải sang trái.

Với 9045: cộng 5 và giữ lại 904, cộng 4 và giữ lại 90, cộng 0 và giữ lại 9, cộng 9 và giữ lại 0. Vòng lặp dừng ở 0 với tổng là 18. Với n = 0, vòng lặp không chạy và đáp án là 0.

Có d bước và chỉ có hai số nguyên trong bộ nhớ: độ phức tạp thời gian O(d), độ phức tạp không gian O(1). Mọi giá trị trung gian đều nhỏ hơn n, nên không thể xảy ra tràn số.

Thuật toán

Đặt total = 0.
Khi n > 0, cộng n % 10 vào total.
Chia n cho 10, bỏ phần thập phân.
Khi n bằng 0, trả về total.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

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

Dùng / khi ngôn ngữ hiểu toán tử này là phép chia thực. Trong JavaScript, TypeScript, Lua, PHP và R, 9045 / 10 cho kết quả 904.5, nên vòng lặp cộng các phần thập phân. Làm tròn xuống bằng Math.floor hoặc math.floor; trong Python, dùng //, trong Dart dùng ~/, trong PHP dùng intdiv, trong R dùng %/%.
Cộng ký tự thay vì chữ số. Ký tự '7' có mã 55, không phải 7.
Lặp khi n >= 10. Chữ số đầu tiên vẫn nằm trong n và chưa được cộng, nên 9045 cho kết quả 9 thay vì 18.
Chuyển số lớn thành văn bản trong R. as.character(100000) cho kết quả "1e+05"; hãy dùng format(n, scientific = FALSE).

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

Độ phức tạp thời gian của việc tính tổng các chữ số của một số là bao nhiêu?

Mỗi chữ số tương ứng với một bước, nên độ phức tạp là O(d), trong đó d là số chữ số. Một số n có khoảng log10(n) + 1 chữ số, nên người ta thường viết cùng giới hạn này là O(log n). Với số nguyên 32 bit, số bước nhiều nhất là 10.

Căn số của một số là gì?

Đó là kết quả khi bạn cộng các chữ số hết lần này đến lần khác cho đến khi chỉ còn một chữ số: 9045 cho ra 18, rồi 9. Với n dương, kết quả bằng 1 + (n-1) % 9, vì mọi số đều có cùng số dư khi chia cho 9 như tổng các chữ số của nó.

Phiên bản chuỗi hay phiên bản số học tốt hơn?

Cả hai đều có độ phức tạp O(d) và đều đúng. Cách dùng chuỗi ngắn hơn trong nhiều ngôn ngữ nhưng tạo ra một bản sao các chữ số. Cách dùng phép tính số học cần thêm bộ nhớ O(1) và cho thấy bạn hiểu cách % 10 và / 10 tách một số thành từng phần. Kiến thức này sẽ hữu ích với các bài toán về số đối xứng và đảo ngược chữ số.

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

Kiểm thử #1

Kiểm thử #2

Đối số

n = 9045

Đầu ra mong đợi