ในปัญหานี้ เราได้รับค่าสามค่า L, R และ d งานของเราคือพิมพ์ ตัวเลขดี . ทั้งหมด อยู่ในช่วง L ถึง R ที่ไม่มี d เป็นตัวเลข
เลขเด็ด คือจำนวนที่ทุกหลักมากกว่าผลรวมของหลักทางขวา (บิตที่มีนัยสำคัญน้อยกว่าทั้งหมด) ตัวอย่างเช่น 732 เป็นจำนวนที่ดี 7> 3+2 และ 3>2
ทีนี้มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: L = 400 , R = 500 , k = 3 Output: 410, 420, 421
คำอธิบาย − ตัวเลขที่ดีระหว่าง 400 ถึง 500 คือ −
410, 420, 421, 430, but we cannot use 3 so 430 is not printed.
ในการแก้ปัญหานี้ เราจะตรวจสอบตัวเลขทั้งหมดในช่วงที่กำหนด เช่น L ถึง R หากตัวเลขเป็นตัวเลขที่ดีและตัวเลขใดๆ ไม่เท่ากับ k ให้พิมพ์ออกมา มิฉะนั้น ให้ปล่อยไว้
ตรวจเลขดี − เราจะสำรวจตัวเลขจากขวาไปซ้าย และรักษาผลรวม ณ จุดใด ๆ หากผลรวมมากกว่าตัวเลขถัดไปจะส่งกลับเท็จ
ตัวอย่าง
มาดูโปรแกรมเพื่อแสดงอัลกอริธึมด้านล่างกัน −
#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;
} ผลลัพธ์
All good numbers from 400 to 600 that do not contain 3 are − 410 420 421 510 520 521 540
