Blog

Problem link

আলোচনাঃ

প্রশ্নে বলা আছে যে, আমাকে এমন একটা নম্বর N বের করতে হবে যার ফ্যাক্টরিয়ালে  Q  সংখ্যক  “ 0(শূণ্য) “ থাকবে।

প্রথম কেস টা নিয়ে চিন্তা করা যাক,

Q = 1 , তার মানে আমাকে এমন একটা নাম্বার বের করা লাগবে যার ফ্যাক্টরিয়ালে ১টা শূণ্য আছে। কিন্ত N বের করার একটা শর্ত দেয়া আছে আর তা হলো  N এর মান সবথেকে ছোট হতে হবে। ব্যাপার টা একটু বুঝা যাক।

        ধরা যাক আমাকে Q = 1 দিল। তাহলে শেষে একটা 0 আছে এমন একটা N হতে পারে 5 কিংবা 6। কারণ 5!=120 আবার 6!=720। কিন্তু আমাদের আন্সার হবে 5। কারণ N=6 থেকে N=5 ছোট।

উত্তরঃ

N! এর শেষে কয়টা 0 আছে তা কি করে বুঝব?      

এখন ভাববার বিষয় হচ্ছে N! এর শেষে কয়টা 0 আছে সেটাই বা কি করে বুঝব? কারণ Q এর সর্বোচ্চ মান হতে পারে 10^8 । মজার ব্যাপার হলো ফ্যাক্টরিয়াল এর শেষে কয়টা 0 আছে তা একটু বুদ্ধি খাটিয়ে খুব সহজেই বের করা যায়। কিভাবে?

        কোনো একটা সংখ্যায় 0 থাকে তখনই যখন তার মধ্যে 10 থাকে।

আর 10 হয় 2*5 করলে। তাহলে প্রশ্ন হচ্ছে 8*7*9 করলে কি তার শেষে 0 থাকবে কিনা? উত্তর = না। কারণ 8 কে আমরা 2*2*2 লিখতে পারি এবং 9 কে 3*3 লিখতে পারি। তাহলে 8*7*9= 2*2*2*7*3*3 লিখতে পারি। এখানে 2 থাকলেও 5 কিন্তু নাই। 5 না থাকার কারণে এখানে 2*5=10 কখনই হবে না। তাহলে আমরা কি বলতে পারি না যে, কোনো একটা নাম্বার এ 10 থাকবে তখনই যখন তার মধ্যে 5 থাকবে। তাহলে 8*7*5 করলে কি 0 পাবো? হ্যাঁ পাবো। কারণ তাহলে 8*7*5= 2*2*2*7*5 লিখতে পারি। আর এখানে 2*5=10 হচ্ছে। এখানে আরও 2টা 2 বাকি আছে কিন্তু 5 না থাকার কারণে তারা 10 বানাতে পারবে না।

n = 5:  5! (1*2 * 3 * 4*5) = (1*2*3*2*2*5) So count of trailing 0s is 1.

n = 8:  8! (1*2*3*4*5*6*7*8) = (1*2*3*2*2*5*2*3*7*2*2*2) So count of trailing 0s is 1 .

N! যেহেতু 1-n পর্যন্ত সব সংখ্যার গুণফল তাই এখানে 5 থেকে 2 এর সংখ্যা বেশি হবেই।

তাই কোনো একটা নাম্বার এ কয়টা 5 আছে সেটা বের করতে পারলেই সেই নাম্বার এ কয়টা 10 আছে সেটা বের করতে পারবো। তাহলে কোনো সংখ্যায় যতগুলো 5 থাকবে ততগুলো 10 থাকবে।

তাহলে যদি বলে 420! এর শেষে কয়টি 0 আছে। তাহলে আমরা নিচের উপায়ে বের করতে পারি-

        420/5=84

        84/5=16

        16/5=3

        3/5=0

OR,

        420/5=84 [ number of 5 is one = 5, 15 ]

       420/5^2=16 [ number of 5 is two = 25, 50 ]

        420/5^3=3 [ number of 5 is three = 125 ]

420/5^4= 0 [ number of 5 is four ]

যখন 0 আসবে তখন থামব। তাহলে 420! এ 84+16+3=103 টি 0 আছে।

আর যেহেতু সবথেকে ছোট নাম্বার বের করা লাগবে তার জন্য আমাদের

Lower bound বের করা লাগবে। কারণ key থেকে strictly বড় বা key এর সমান কোনো ভ্যালু আমাদের range এ আছে কিনা তা বের করাই Lower bound এর কাজ।

                ধরা যাক, আমাদের নিচের range এ 5 আছে কিনা তা আমাদের বের করা লাগবে। এর জন্য বাইনারি সার্চ করব।

1) mid= low+(high-low)/2= 0+(5-0)/2 = 2 no index

        2নং ইনডেক্স এ কিন্তু আমাদের কাংক্ষিত key=5 পেয়ে গেছি কিন্তু তারপর ও সার্চ করা থামাবো না কারণ আমাদের দেখা লাগবে যে, 2নং ইনডেক্স এর আগের 0 আর 1 নাম্বার ইনডেক্স এ 5 পাওয়া যায় কিনা। আর এই জিনিস টাই Lower bound দিয়ে বের করা যায়।

          Now, low=0 and high=mid-1=1

2) mid= low+(high-low)/2= 0+(1-0)/2 = 0 no index value = 1

          Now, low=1 and high=1

3) mid= low+(high-low)/2= 1+(1-1)/2 = 1 no index value = 5

          So, finally we get our desired key . As we find our key that’s why we will return this key value=5. Otherwise, it will return “-1” .Suppose in index 1,the value of that index is 3 and it didn’t match with our desired key. Then we will return “-1”.

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI acos(-1.0)
#define MOD 1,000,000,007
const int N=105;

int countFive(int n){
 
    int cnt=0;
    while(n>0){
        cnt+=(n/5);
        n/=5;
    }
    return cnt;
}

int main(){
 
    int t,c=1,n;
 
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
           // lower bound code start
        int l=0,r=1e9+1,m,ans=-1;
        while(l<=r){
            m=l+(r-l)/2;
            if(countFive(m)>=n){
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
           // lower bound code end
        if(countFive(ans)==n) printf("Case %d: %d\n",c,ans);
        else printf("Case %d: impossible\n",c);
        c++;
 
    }
}

----------------------------------- OR -------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI acos(-1.0)
#define MOD 1,000,000,007
const int N=105;

int countFive(int n){
    int count = 0; 
    for (int i = 5; n / i >= 1; i *= 5) 
        count += n / i;
    return count;
}

int main(){
 
    int t,c=1,n;
 
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
           // lower bound code start
        int l=0,r=1e9+1,m,ans=-1;
        while(l<=r){
            m=l+(r-l)/2;
            if(countFive(m)>=n){
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
           // lower bound code end
        if(countFive(ans)==n) printf("Case %d: %d\n",c,ans);
        else printf("Case %d: impossible\n",c);
        c++;
 
    }
}