একটি সংখ্যা Y দেওয়া থাকলে, সর্বনিম্ন X বের করতে হবে যাতে X!-এ কমপক্ষে Yটি ট্রেইলিং জিরো (trailing zeros) থাকে। উদাহরণস্বরূপ, Y = 2 হলে X = 10। কারণ 10! = 3228800, যাতে ২টি জিরো রয়েছে।
এটি বাইনারি সার্চ (binary search) দিয়ে সমাধান করা যায়। N!-এ ট্রেইলিং জিরোর সংখ্যা N!-এ ৫-এর ফ্যাক্টরের সংখ্যা দ্বারা নির্ণয় হয়। X বের করতে [0, 5*Y] রেঞ্জে বাইনারি সার্চ করা হয়।
উদাহরণ
#include<iostream> using namespace std; int factorCount(int n, int X) { if (X < n) return 0; return (X / n + factorCount(n, X / n)); } int findX(int Y) { int left = 0, right = 5 * Y; int N = 0; while (left <= right) { int mid = (right + left) / 2; if (factorCount(5, mid) < Y) { left = mid + 1; }else { N = mid; right = mid - 1; } } return N; } int main() { int Y = 4; cout << "Smallest value of X: " << findX(Y); } আউটপুট
Smallest value of X: 20
