Chúng ta được cho một số d đại diện cho số chữ số. Mục đích là để tìm số lượng các số nguyên dương có 0 là một chữ số và có tối đa d chữ số. Đếm tất cả các số dương có 1 chữ số, 2 chữ số, 3 chữ số… .d chữ số có chứa ít nhất một chữ số 0.
Đầu tiên chúng ta sẽ tìm các số đếm các số có d chữ số với ít nhất một 0. Giả sử d =3. Để tạo một số có 3 chữ số với ít nhất một 0, các cách có thể thực hiện là -
Here d1 can have 1 to 9 : 9 ways d2 can have 0-9 : 10 ways d3 can have 0-9 : 10 ways Total numbers possible: 9 x 10 x 10 = 9 x 102 For d digits, count of numbers: 9 x 10d-1 For d digits, numbers without any 0 are : 9d Total numbers having d digits with at least one 0 = 9 x 10d-1 - 9d = 9 x ( 10d-1 - 9d-1 )
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - d =4
Đầu ra - Đếm số nguyên dương có 0 là một chữ số và các chữ số 'd' lớn nhất là - 2619
Giải thích - số chữ số x có ít nhất một chữ số 0 -
1 digit numbers : 0 2 digit numbers : 9 3 digit numbers : 171 4 digit numbers: 2439 Total= 9+171+2439 = 2619
Đầu vào - d =1
Đầu ra - Đếm số nguyên dương có 0 là một chữ số và các chữ số 'd' lớn nhất là - 0
Giải thích - Từ 1 đến 9 không có số nào có 0 là 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 vòng lặp for. Bắt đầu chuyển từ chữ số 1 đến chữ số d và tính toán các số bằng công thức được đề cập ở trên. Thêm giá trị trả về để đếm.
-
Lấy số nguyên d cho các chữ số.
-
Hàm total_count (int d)) nhận một số chữ số d và trả về tổng số các chữ số d và có ít nhất một chữ số 0.
-
Tính các số như temp =9 * (pow (10, d-1) - pow (9, d-1));
-
Nhiệt độ trở lại.
-
Hàm Maximum_d (int d) nhận số chữ số tối đa d và trả về số lượng các số có tối đa d chữ số có ít nhất một chữ số 0.
-
Di chuyển bằng cách sử dụng một vòng lặp bắt đầu từ các số 1 chữ số rồi đến 2 và cứ tiếp tục như vậy cho đến d.
-
Với mỗi d, hãy tính toán các số dưới dạng tổng_lượng (i). Thêm cái này để đếm.
-
Cuối cùng, chúng tôi sẽ nhận được tổng số.
-
Kết quả là số lượt trả lại.
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ẽ tính toán số lượng bằng cách quan sát G.P được hình thành cho các phép tính trên.
Solution is 9 x (10d-1 - 9d-1) = 9 x (10d - 1)- 9 x (9d-1) = 9 x (10i - 1) - 9 x (9i - 1) ( 1<=i<=d ) = g.p 1 - g.p 2 = 9x(10d-1)/(10-1) - 9x(9d-1)/(9-1) = (10d-1)- (9/8)*(9d-1)
-
Lấy d là số chữ số tối đa.
-
Hàm Maximum_d (int d) nhận số chữ số tối đa d và trả về số lượng các số lên đến d chữ số có ít nhất một chữ số 0.
-
Sử dụng công thức trên tính temp_1 là 9 * ((pow (10, d) -1) / 9).
-
Tính temp_2 là 9 * ((pow (9, d) -1) / 8).
-
Đặt số lượng =temp_1 - temp_2.
-
Kết quả là số lượt trả lại.
Ví dụ (cách tiếp cận ngây thơ)
#include<bits/stdc++.h>
using namespace std;
int total_count(int d){
int temp = 9*(pow(10,d-1) - pow(9,d-1));
return temp;
}
int maximum_d(int d){
int count = 0;
for (int i=1; i<=d; i++){
count = count + total_count(i);
}
return count;
}
int main(){
int d = 5;
cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
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 positive integers with 0 as a digit and maximum 'd' digits are: 33570
Ví dụ (Cách tiếp cận hiệu quả)
#include<bits/stdc++.h>
using namespace std;
int maximum_d(int d){
int temp_1 = 9*((pow(10,d)-1)/9);
int temp_2 = 9*((pow(9,d)-1)/8);
int count = temp_1 - temp_2;
return count;
}
int main(){
int d = 4;
cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
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 positive integers with 0 as a digit and maximum 'd' digits are: 2619