এই সমস্যায় আমরা সবচেয়ে বড় কে-ডিজিটের সংখ্যা খুঁজে বের করার চেষ্টা করব, যেটি X দ্বারা বিভাজ্য হবে। এই কাজটি করার জন্য আমরা এই সূত্রটি (10^k) – 1) দ্বারা সবচেয়ে বড় K সংখ্যার সংখ্যা নেব। তারপর পরীক্ষা করুন সংখ্যাটি X দ্বারা বিভাজ্য কি না, যদি না হয়, আমরা এই সূত্রটি ব্যবহার করে সঠিক সংখ্যাটি পাব।
𝑚𝑎𝑥−(𝑚𝑎𝑥 𝑚𝑜𝑑 𝑋)
একটি উদাহরণ হল একটি 5-সংখ্যার সংখ্যার মতো, যা 29 দ্বারা বিভাজ্য। তাই বৃহত্তম 5-অঙ্কের সংখ্যাটি 99999। এটি 29 দ্বারা বিভাজ্য নয়। এখন সূত্রটি প্রয়োগ করলে আমরা পাব −
99999−(99999 𝑚𝑜𝑑 29)=99999−7=99992
99992 সংখ্যাটি 29 দ্বারা বিভাজ্য।
অ্যালগরিদম
maxKDigit(k, x)
begin max = (10^k) - 1 if max is divisible by x, return max otherwise return max – (max mod x) end
উদাহরণ
#include<iostream>
#include<cmath>
using namespace std;
long max_k_digit(int k, int x){
//get the maximum number of k digits
int max = pow(10, k) - 1;
if(max % x == 0){
return max;
}
return (max) - (max % x);
}
main() {
int k, x;
cout << "Enter Digit Count(K) and Divisor(N): ";
cin >> k >> x;
cout << "Result is: " << max_k_digit(k, x);
} আউটপুট
Enter Digit Count(K) and Divisor(N): 5 29 Result is: 99992
আউটপুট
Enter Digit Count(K) and Divisor(N): 6 87 Result is: 999978
