Coin Change With Bitset | DP Series(Episode-7)
এই পর্বটি পড়ার পূর্বে বিটসেট সম্পর্কে ভালোভাবে জানতে হবে।
Problem:
মনে কর, তোমাকে n<=1000 টি কয়েন দেয়া আছে যাদের ভ্যালু coin[i]<=100000। বলতে হবে এই কয়েনগুলো ব্যাবহার করে 1 to 10^5 পর্যন্ত কয়টি ভিন্ন ভিন্ন ভ্যালু বানানো যায়?
Solution:
মনে করি, আমার কয়েন গুলোর সেট হচ্ছে, {১ , ৩ , ৬}। ১ থেকে ১০ পর্যন্ত কয়টি ভিন্ন ভিন্ন ভ্যালু বানানো যায় সেটি বের করতে হবে।
১) আমরা একটি বিটসেট অ্যারে নিবো 11 সাইজের। যার প্রতিটি ইনডেক্স এ 0 থাকবে প্রাথমিক অবস্থায়।
২) এখন শুরুতে ধরে নিবো কয়েনগুলো দ্বারা আমি ০ ভ্যালু বানাতে পারবো। তাহলে bset = 00000000001
৩) এখন, আমার প্রথম কয়েন ১ টাকার। অর্থাৎ, ইতোপূর্বে আমি যতো যতো টাকার ভ্যালু বানাতে পেরেছি তাদের সবার সাথে ১ যোগ করলে যে নতুন ভ্যালুগুলো পাবো সেগুলোও বানানো সম্ভব।
ইতোপূর্বে আমি ০ টাকা বানাতে পেরেছি। অর্থাৎ, নতুন করে ১টাকা বানাতে পারবো।
এখন পর্যন্ত বানাতে পেরেছি {১ , ০}
এখন, আমার ২য় কয়েন ৩ টাকার। অর্থাৎ, ইতোপূর্বে আমি যতো যতো টাকার ভ্যালু বানাতে পেরেছি তাদের সবার সাথে ৩ যোগ করলে যে নতুন ভ্যালুগুলো পাবো সেগুলোও বানানো সম্ভব।
অর্থাৎ, নতুন করে বানাতে পারবো ৩ এবং ৪ টাকা।
এখন পর্যন্ত বানাতে পেরেছি {৪, ৩, ১, ০}
এখন, আমার ৩য় কয়েন ৬ টাকার। অর্থাৎ, ইতোপূর্বে আমি যতো যতো টাকার ভ্যালু বানাতে পেরেছি তাদের সবার সাথে ৬ যোগ করলে যে নতুন ভ্যালুগুলো পাবো সেগুলোও বানানো সম্ভব।
অর্থাৎ, নতুন করে বানাতে পেরেছি ৬, ৭, ৯, ১০ টাকা।
এখন পর্যন্ত বানাতে পেরেছি {০, ১, ৩, ৪, ৬, ৭, ৯, ১০}
৪) একটু ভালোভাবে লক্ষ্য করলে দেখবে আমি বর্তমানে x টাকার কয়েন নিয়ে কাজ করলে এখন পর্যন্ত পাওয়া বিটসেট এর সাথে এই একই বিটসেটের একটি কপি কে x ঘর Left Shift করে OR করলেই শুরু থেকে এই কয়েন পর্যন্ত ব্যাবহার করে কি কি ভ্যালু বানাতে পেরেছি তাদের ইনডেক্স এর বিট অন হয়ে যায়!!!
৫) সবশেষে, বিটসেটের ১ থেকে ১০^৫ ইনডেক্স পর্যন্ত যতোগুলো বিট অন আছে ততোগুলো ভিন্ন ভিন্ন ভ্যালু বানানো সম্ভব।
এবার কোড দেখা যাকঃ
Comments
Post a Comment