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