ধরুন আমাদের একটি ফাংশন f(x), এটি x এর ফ্যাক্টোরিয়ালের শেষে শূন্যের সংখ্যা প্রদান করবে। সুতরাং f(3) =0 এর জন্য কারণ 3! =6 এর শেষে কোন শূন্য নেই, যখন f(11) =2 কারণ 11! =39916800 এর শেষে 2টি শূন্য রয়েছে। এখন যখন আমাদের K থাকে, তখন আমাদের খুঁজে বের করতে হবে কতটি অ-ঋণাত্মক পূর্ণসংখ্যা x এর সম্পত্তি আছে যেটি f(x) =K।
সুতরাং ইনপুট যদি K =2 এর মত হয়, তাহলে উত্তর হবে 5।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন ঠিক করুন (), এটি x লাগবে,
- ret :=0
- আরম্ভ করার জন্য i :=5, যখন i <=x, আপডেট i :=i * 5, do −
- ret :=ret + x / i
- রিটার্ন রিটার্ন
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- যদি K 0 এর সমান হয়, তাহলে −
- রিটার্ন ৫
- নিম্ন :=1, উচ্চ :=K * 5
- যখন কম <উচ্চ, কর −
- মধ্য :=নিম্ন + (উচ্চ - নিম্ন) /2
- x :=ঠিক আছে(মধ্য)
- যদি x
- নিম্ন :=মধ্য + 1
- অন্যথায়
- উচ্চ :=মধ্য
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli ok(lli x){
int ret = 0;
for(lli i = 5; i <= x; i *= 5){
ret += x / i;
}
return ret;
}
int preimageSizeFZF(int K) {
if(K == 0) return 5;
lli low = 1;
lli high = (lli)K * 5;
while(low < high){
lli mid = low + (high - low) / 2;
lli x = ok(mid);
if(x < K){
low = mid + 1;
}else high = mid;
}
return ok(low) == K ? 5 : 0;
}
};
main(){
Solution ob;
cout << (ob.preimageSizeFZF(2));
} ইনপুট
2
আউটপুট
5
