Chúng tôi được cung cấp một số N làm đầu vào. Mục đích là để đếm tổng số chữ số giữa các số từ 1 đến N. Các số từ 1 đến 9 yêu cầu mỗi chữ số 1, 11 đến 99 yêu cầu mỗi chữ số 2, 100 đến 999 yêu cầu mỗi chữ số 3, v.v.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - N =11
Đầu ra - Tổng số chữ số từ 1 đến N là:13
Giải thích - Các số từ 1 đến 9 mỗi số có 1 chữ số:9 chữ số 10, 11 mỗi số có 2 chữ số. 4 chữ số. Tổng các chữ số =9 + 4 =13.
Đầu vào - N =999
Đầu ra - Số tổng các chữ số từ 1 đến N là:2889
Giải thích - Các số từ 1 đến 9 mỗi số có 1 chữ số:9 chữ số 10 đến 99 mỗi số có 2 chữ số. :180 chữ số. Từ 100 đến 999 có 3 chữ số, mỗi chữ số:2700 chữ số Tổng các chữ số =2700 + 180 + 9 =2889 chữ số
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ sử dụng hai cách tiếp cận. Một cách tiếp cận ngây thơ đầu tiên sử dụng một hàm đệ quy để tính toán các chữ số trong một số num. Chuyển đổi num đã truyền thành một chuỗi. Độ dài của chuỗi là các chữ số trong num. Thực hiện điều này cho mỗi số bỏ qua num-1 hiện tại một cách đệ quy.
-
Lấy một số dưới dạng số nguyên dương.
-
Hàm total_digits (int num) lấy số và trả về chữ số trong các số từ 1 đến num.
-
Để tính toán các chữ số trong num, hãy chuyển đổi num thành chuỗi. (to_string (num)).
-
Độ dài của chuỗi là các chữ số trong num.
-
Nếu num là 1 thì trả về 1. Độ dài trả về khác + total_digits (num-1) cho các số còn lại nhỏ hơn num.
-
Cuối cùng, chúng tôi sẽ nhận được tổng số chữ số là kết quả.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ sử dụng logic rằng với mỗi số lên đến N. Chúng tôi sẽ duyệt 10, 100, 1000 cho đến N. Với mỗi 10i, số chữ số là (num-i + 1).
-
Lấy một số dưới dạng số nguyên dương.
-
Hàm total_digits (int num) lấy số và trả về chữ số trong các số từ 1 đến num.
-
Lấy tổng số ban đầu là 0.
-
Đảo chiều i =1 đến i <=num, tăng i lên 10 trong mỗi lần lặp và thêm num-i + 1 để đếm.
-
Kết quả là trả về số lượng ở cuối vòng lặp for.
Ví dụ (cách tiếp cận ngây thơ)
#include <bits/stdc++.h>
using namespace std;
int total_digits(int num){
string str = to_string(num);
int length = str.length();
if (num == 1){
return 1;
}
return length + total_digits(num - 1);
}
int main(){
int num = 20;
cout<<"Count of total number of digits from 1 to n are: "<<total_digits(num);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of total number of digits from 1 to n are: 31
Ví dụ (Cách tiếp cận hiệu quả)
#include <bits/stdc++.h>
using namespace std;
int total_digits(int num){
int count = 0;
for(int i = 1; i <= num; i *= 10){
count = count + (num - i + 1);
}
return count;
}
int main(){
int num = 20;
cout<<"Count of total number of digits from 1 to n are: "<<total_digits(num);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of total number of digits from 1 to n are: 31