मान लीजिए कि हमारे पास एक फ़ंक्शन f(x) है, यह x के फ़ैक्टोरियल के अंत में शून्यों की संख्या लौटाएगा। तो f(3) =0 के लिए क्योंकि 3! =6 के अंत में कोई शून्य नहीं है, जबकि f(11) =2 क्योंकि 11! =39916800 के अंत में 2 शून्य हैं। अब जब हमारे पास K है, तो हमें यह पता लगाना होगा कि कितने गैर-ऋणात्मक पूर्णांक x में यह गुण है कि f(x) =K.
तो अगर इनपुट K =2 जैसा है, तो उत्तर 5 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें ठीक (), इसमें x लगेगा,
- रिट:=0
- इनिशियलाइज़ i :=5 के लिए, जब i <=x, अपडेट i :=i * 5, करें -
- रिट:=रिट + एक्स / आई
- रिटर्न रिटर्न
- मुख्य विधि से, निम्न कार्य करें -
- यदि K, 0 के समान है, तो −
- 5 वापसी
- निम्न:=1, उच्च:=के * 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