Trong bài toán này, chúng ta có ba giá trị L, R và d. Nhiệm vụ của chúng tôi là in tất cả số đẹp trong phạm vi từ L đến R không chứa chữ số d.
Một con số tốt là một số trong đó mọi chữ số đều lớn hơn tổng các chữ số ở bên phải của nó (tất cả các bit nhỏ hơn nó). Ví dụ:732 là một số đẹp, 7> 3 + 2 và 3> 2.
Bây giờ, hãy lấy một ví dụ để hiểu vấn đề,
Input: L = 400 , R = 500 , k = 3 Output: 410, 420, 421
Giải thích - những con số tốt từ 400 đến 500 là -
410, 420, 421, 430, but we cannot use 3 so 430 is not printed.
Để giải quyết vấn đề này, đối với điều này, chúng tôi sẽ kiểm tra tất cả các số trong phạm vi đã cho, tức là từ L đến R, nếu một số là số tốt và bất kỳ chữ số nào của nó không bằng k, thì hãy in ra nếu không thì bỏ đi.
Kiểm tra số tốt - chúng tôi sẽ duyệt số từ phải sang trái và duy trì một tổng, tại bất kỳ thời điểm nào nếu tổng lớn hơn số tiếp theo trả về false.
Ví dụ
Hãy xem chương trình để minh họa thuật toán bên dưới -
#include<bits/stdc++.h>
using namespace std;
bool isvalidNumber(int n, int d){
int digit = n%10;
int sum = digit;
if (digit == d)
return false;
n /= 10;
while (n){
digit = n%10;
if (digit == d || digit <= sum)
return false;
else{
sum += digit;
n /= 10;
}
}
return 1;
}
void printGoodNumbersLtoR(int L, int R, int d){
for (int i=L; i<=R; i++){
if (isvalidNumber(i, d))
cout << i << " ";
}
}
int main(){
int L = 400, R = 600, d = 3;
cout<<"All good numbers from "<<L<<" to "<<R<<" that do not contain "<<d<<" are :\n";
printGoodNumbersLtoR(L, R, d);
return 0;
} Đầu ra
All good numbers from 400 to 600 that do not contain 3 are − 410 420 421 510 520 521 540