মনে করুন, f(x) একটি ফাংশন যা x-এর ফ্যাক্টোরিয়ালের শেষে কতটি শূন্য আছে তা রিটার্ন করে। যেমন, f(3) = 0 কারণ 3! = 6-র শেষে শূন্য নেই, f(11) = 2 কারণ 11! = 39916800-র শেষে ২টি শূন্য আছে। এখন K দেওয়া থাকলে, কতগুলো অ-ঋণাত্মক পূর্ণসংখ্যা x আছে যাতে f(x) = K, তা বের করতে হবে।
যেমন, K = 2 হলে, উত্তর হবে ৫।
সমাধানের ধাপসমূহ
- ok() ফাংশন সংজ্ঞায়িত করুন যা x নিবে
- ret := 0
- i := 5 থেকে x পর্যন্ত i *= 5 করলে ret += x / i
- ret রিটার্ন করুন
- মূল ফাংশন থেকে:
- যদি K == 0 হয়, ৫ রিটার্ন করুন
- low := 1, high := K * 5
- যখন low < high
- mid := low + (high - low) / 2
- x := ok(mid)
- যদি x < K হয়, low := mid + 1, অন্যথায় high := mid
- রিটার্ন করুন (ok(low) == K ? 5 : 0)
উদাহরণ
#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
