Link: https://www.hackerrank.com/contests/intra-aust-preliminary-round-senior-group/challenges
আমাকে N দেয়া হবে এবং আমার ১ থেকে N পর্যন্ত সব ইন্টিজার এর বাইনারি রিপ্রেসেন্টেশন এ কতটি ১ আছে, তা বলতে হবে। ধরি N = ৮। উপরের চিত্র তে আমি ০ থেকে ৮ পর্যন্ত সংখ্যাগুলির বাইনারি লিখেছি। লক্ষ্য করলে দেখা যায়, এই বাইনারি এর মাঝে একটি নির্দিষ্ট সময় পরপর ১ আসে। প্রথম ঘর এর জন্য একটি ০, একটি ১, এভাবে, দ্বিতীয় ঘরের জন্য দু'টি ০, দু'টি ১, এভাবে... খেয়াল করলে দেখা যায় ব্যাপারটা আসলে ২ এর পাওয়ার হিসেবে আসতে থাকে। আমরা বাইনারি নম্বর এর এই ব্যাপারগুলি অবশ্যি জানি। এখন আমি এই জিনিসটি থেকে একটি প্যাটার্ন বানানোর চেষ্টা করবো।
যেহেতু আমার N জানা আছে, কাজেই প্রথমে N এর বাইনারি বের করে ফেলি। ৮ এর ক্ষেত্রে ১০০০। এখন খেয়াল করি, (ডান দিক থেকে ০ - ৮ সকল নম্বর) প্রথম ঘরে, ০ থেকে ৮ এর মাঝে ১ আছে মোট ৪ টি। দ্বিতীয় ঘরেও ৪ টি, তৃতীয় ঘরেও ৪ টি, চতুর্থ ঘরে ১ টি। মোট ১৩ টি ১ আছে। প্রতি ঘরের জন্য এই ১ এর কাউন্ট টা কিভাবে করবো ? কিছু টেস্টকেস চিন্তা করলে ব্যাপারটা সবার ধরতে পারার কথা। প্যাটার্ন বের করতে পারলে ভালো, নাহলে চিত্রের বামদিকে আমি আমার প্যাটার্ন এর ফরমুলা লিখে দিয়েছি। এখানে xtra জিনিসটি একটু ইম্পরটেন্ট। নরমালি আমরা ১,২,৪,৮,১৬... ২ এর পাওয়ার এর ব্যাপারগুলি সহজে প্যাটার্ন এ ফেলেতে পারি, কিন্তু যদি ৯,১৩,২১,...এরকম নম্বর থাকে, যেটা আসলে কমপ্লিট প্যাটার্ন এর মধ্যে পরে না, তাদের জন্য বারতি কিছু যোগ এর দরকার হয়। ৯ এর জন্য চিন্তা করলে এমনটা দেখা যাবে। যাহোক, এখানে ব্যাপারটা হল N এর বাইনারির length পর্যন্ত আমাকে লুপ চালায়ে আর কিছু ক্যালকুলেশন করে টোটাল কতটি ১ আছে তা বের করতে হবে।
আমাকে N দেয়া হবে এবং আমার ১ থেকে N পর্যন্ত সব ইন্টিজার এর বাইনারি রিপ্রেসেন্টেশন এ কতটি ১ আছে, তা বলতে হবে। ধরি N = ৮। উপরের চিত্র তে আমি ০ থেকে ৮ পর্যন্ত সংখ্যাগুলির বাইনারি লিখেছি। লক্ষ্য করলে দেখা যায়, এই বাইনারি এর মাঝে একটি নির্দিষ্ট সময় পরপর ১ আসে। প্রথম ঘর এর জন্য একটি ০, একটি ১, এভাবে, দ্বিতীয় ঘরের জন্য দু'টি ০, দু'টি ১, এভাবে... খেয়াল করলে দেখা যায় ব্যাপারটা আসলে ২ এর পাওয়ার হিসেবে আসতে থাকে। আমরা বাইনারি নম্বর এর এই ব্যাপারগুলি অবশ্যি জানি। এখন আমি এই জিনিসটি থেকে একটি প্যাটার্ন বানানোর চেষ্টা করবো।
যেহেতু আমার N জানা আছে, কাজেই প্রথমে N এর বাইনারি বের করে ফেলি। ৮ এর ক্ষেত্রে ১০০০। এখন খেয়াল করি, (ডান দিক থেকে ০ - ৮ সকল নম্বর) প্রথম ঘরে, ০ থেকে ৮ এর মাঝে ১ আছে মোট ৪ টি। দ্বিতীয় ঘরেও ৪ টি, তৃতীয় ঘরেও ৪ টি, চতুর্থ ঘরে ১ টি। মোট ১৩ টি ১ আছে। প্রতি ঘরের জন্য এই ১ এর কাউন্ট টা কিভাবে করবো ? কিছু টেস্টকেস চিন্তা করলে ব্যাপারটা সবার ধরতে পারার কথা। প্যাটার্ন বের করতে পারলে ভালো, নাহলে চিত্রের বামদিকে আমি আমার প্যাটার্ন এর ফরমুলা লিখে দিয়েছি। এখানে xtra জিনিসটি একটু ইম্পরটেন্ট। নরমালি আমরা ১,২,৪,৮,১৬... ২ এর পাওয়ার এর ব্যাপারগুলি সহজে প্যাটার্ন এ ফেলেতে পারি, কিন্তু যদি ৯,১৩,২১,...এরকম নম্বর থাকে, যেটা আসলে কমপ্লিট প্যাটার্ন এর মধ্যে পরে না, তাদের জন্য বারতি কিছু যোগ এর দরকার হয়। ৯ এর জন্য চিন্তা করলে এমনটা দেখা যাবে। যাহোক, এখানে ব্যাপারটা হল N এর বাইনারির length পর্যন্ত আমাকে লুপ চালায়ে আর কিছু ক্যালকুলেশন করে টোটাল কতটি ১ আছে তা বের করতে হবে।
No comments:
Post a Comment