এর আগে একটি সংখ্যার ফ্যাক্টরিয়ালের শেষে কতগুলো শুন্য আছে তা কিভাবে কাউন্ট করে বের করা যায় তা নিয়ে লিখেছিলাম। এরই ধারাবাহিকতায় আজকের এই পোস্টঃ

Light OJ এর এই প্রবলেমকে(1090 – Trailing Zeroes (II)) আমরা তিনটি পার্টে বিভক্ত করে সল্ভ করার চেস্টা করব।

প্রথম পার্টঃ nCr এর জন্য ক্যালকুলেশন,

দ্বিতীয় পার্টঃ N^p এর জন্য ক্যালকুলেশন।

তৃতীয় পার্টঃ এই অংশে আমরা প্রথম পার্ট এবং দ্বিতীয় পার্টকে একসাথে করে ফাইনাল রেজাল্ট বের করব।

প্রথম পার্টঃ  nCr এর জন্য ক্যালকুলেশন

এই সূত্রটি আমারা সকলেই জানিঃ

ncrট্রেইলিং জিরো হিসেব করতে n!, r! এবং (n – r)! এর জন্য কিভাবে 2 এবং 5 কাউন্ট করে বের করব সেটা নিয়ে আলোচনা এখানে  আছে, দেখে নিতে পারো।

যদি n!, r! এবং (n – r)! এর জন্য (২, ৫) এর সংখ্যা যথাক্রমে (i , j), (k, l), (m, n) হয়, তাহলে nCr এর জন্য (২, ৫) এর সংখ্যা হিসেব করব এভাবেঃ

hisebএখানে একটি বিষয় অবশ্যই খেয়াল রাখতে হবে, আমরা শুধু ২ এবং ৫ নিয়ে কাজ করছি, অন্যান্য গুণনীয়ক ২ এবং ৫ এর সাথে গুন আকারে থাকতে পারে, তবে সেটা নিয়ে আমরা মাথা ঘামাব না।

দ্বিতীয় পার্টঃ N^p এর জন্য ক্যালকুলেশন

আমরা জানি “একটি সংখ্যার শেষে যতসংখ্যক শুন্য থাকবে ঐ সংখ্যাটিতে ততসংখ্যক (2 x 5) এর গুনফল উপস্থিত থাকবে।” তাহলে N^p এর ক্ষেত্রে আমরা প্রথমে বের করে নিব N সংখ্যাটিতে কত সংখ্যক (2 x 5) উপস্থিত অর্থাৎ কত সংখ্যক 2 এবং কত সংখ্যক 5 এর গুনফল আকারে সংখ্যাটিকে প্রকাশ করা যায়।

যদি একটি সংখ্যা N কে x সংখ্যক 2 এবং y সংখ্যক 5 এর গুনফল আকারে প্রকাশ করা যায়(অন্যান্য গুননীয়কও থাকতে পারে), তাহলে N এর শেষে min(x, y) সংখ্যক শুন্য উপস্থিত থাকবে। যদি এই লাইনটি বুঝতে প্রবলেম হয় তাহলে ভয় পাওয়ার কারন নেই, একটু পরেই সবটা ক্লিয়ার হয়ে যাবে।

ধরি N = 60 তাহলে আমরা N কে এভাবে লিখতে পারিঃ

pic11এখানে 2 আছে 2  টি 5 আছে 1 টি, সুতরাং,

(2 x 5) আছে ১ টি = N = 60 = (2 x 5) x 2 x 3 = min(x, y) = min(2, 1) [লক্ষ্যনীয়ঃ 3 কে কনসিডারে আনার প্রয়োজন নেই]।

আসলে এখানে তেমন কিছুই করছি না। আমরা N এর গুননীয়ক গুলির মধ্যে ২ এবং ৫ কতবার আছে সেটাই বের করছি।
সুতরাং কত সংখ্যক 2 কিংবা 5 আছে সেটা বের করব এভাবেঃ

int calc_func(int N, int x)
{
    int counter = 0;
    while(N % x == 0)//x দ্বারা N ভাগ গেলে N এ একটি x আছে
    {
        counter++;// x এর সংখ্যা কাউন্ট হচ্ছে
        N = N / x;// একটি x কাউন্ট হয়ে গেলে x দ্বারা N কে ভাগ করে দিতে হবে
    }
    return counter;
}

এখানে,

int calc_func(int N, int x);

এই ফানশনটি আমাদের ক্যাল্কুলেট করে বলে দিবে N এ কতসংখ্যক 2 এবং 5 আছে।

কত সংখ্যক ২ আছে তা বের করার জন্য ফাংশনটি কল করব এভাবেঃ

calc_func(N, 2);

আর কত সংখ্যক ৫ আছে তা বের করার জন্য ফাংশনটি কল করব এভাবেঃ

calc_func(N, 5);

খুব সহজ !!!

তাহলে যদি x সংখ্যক 2 আর y সংখ্যক 5 পাওয়া যায়, সেক্ষেত্রে আমরা N^p এ মোট 2 এবং 5 পাবো যথাক্রমে px এবং py সংখ্যক। কেননাঃ

pic1

এখানে, অন্যান্য গুননীয়কগুলি কনসিডারেশনে আনার দরকার নেই, কারন আমরা শুধু 2 এবং 5 এর সংখ্যা কাউন্ট করব। সুতরাং N^p এর শেষে মোট শুন্য সংখ্যা কাউন্ট করতে হলে মেইন ফাংশনটি দেখতে হবে এরকমঃ

int main()
{
    int N, p;
    scanf("%d %d", &N, &p);

    int count2 = p * calc_func(N, 2);
    int count5 = p * calc_func(N, 5);
    printf("%d trailing zeros.\n", min(count2, count5));

    return 0;
}

তৃতীয় পার্টঃ

প্রথম এবং দ্বিতীয় পার্ট থেকে প্রাপ্ত মান হতে আমারা সহযেই nCr * N^p এর জন্য ২ ও ৫ এর সংখ্যা কাউন্ট করে ফেলতে পারবো এভাবেঃ

trird partকি, খুব মজার না???

তাহলে,


nCr x N^p  এর শেষে মোট শূন্য সংখ্যা = min(i - k - m + px, j - l - n + py);

আমার মনে হয় এই অংশটুকুর কোডিং তোমরা নিজেরাই করে নিতে পারবে, তাই আর কোড করে দিলাম না।

এবার তাহলে সল্ভ করে ফেলোঃ

Light OJ Problems:

1028 – Trailing Zeroes (I)(ডিভিজর কাউন্টিং প্রবলেম)

1090 – Trailing Zeroes (II)

1138 – Trailing Zeroes (III)

কৃতজ্ঞতাঃ

একটি ব্যাপার মাথায় রাখতে হবে, যদি শুধুমাত্র N^p (অর্থাৎ nCr গুন আকারে থাকবে না) এর শেষে শুন্য সংখ্যা হিসেব করার দরকার হয় সেক্ষেত্রে,

N^p এর শেষে শুন্য সংখ্যা = (N এর শেষে শুন্য সংখ্যা) * p

এভাবে হিসেব করলেই হবে, আলাদা ভাবে ২ এবং ৫ কাউন্ট করার দরকার নেই।

এই অংশটুকুর আইডিয়াদাতাঃ আবু সুফিয়ান ভাইয়া

বিষয়টি আমাকে অবগত করার জন্য উনাকে ধন্যবাদ 🙂

Advertisements