201. Bitwise AND of Numbers Range - Leetcode

 201. Bitwise AND of Numbers Range - Leetcode, Medium

প্রবলেম টা একবার পড়লেই বোঝা যাবে, দুইটা নাম্বার দেয়া থাকবে A এবং B।
A থেকে B এর মধ্যে যত গুলা নাম্বার আছে সবার AND(&) করে তাদের রেজাল্ট রিটার্ন করতে হবে।
ধরি A = 2, B  = 10
সুতরাং Ans = 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 = 0

আমরা চাইলেই কিন্তু এইভাবে A থেকে B পর্যন্ত লুপ চালিয়ে এন্সার বের করতে পারি, কিন্তু এক্ষেত্রে সম্ভব না, কারন আমাদের রেঞ্জ হইতে 2*10^9 পর্যন্ত। যেটা অনেক বড় একটা সংখ্যা।


এখন আসি কিভাবে আমরা এই প্রবলেম টা খুব সহজে বিট ম্যানিপুলেশন দিয়ে করে ফেলতে পারি।

পাশের ছবিটার দিকে তাকাই, ১-২০ পর্যন্ত সব গুলা সংখ্যার বাইনারি রিপ্রেজেন্টেশন দেয়া আছে। আপাতত ধরি আমাদের রেঞ্জ [১২,১৫], এদের বাইনারি - 
12 = 1100
13 = 1101
14 = 1110
15 = 1111
আমরা বাইনারি AND(&) এর ক্ষেত্রে জানি, যদি দুইটা বিট ই 1 হয়, তাহলে তাদের AND(&) হবে 1, অন্যসব ক্ষেত্রে 0. এখন ১২ থেকে ১৫ পর্যন্ত আমরা যদি সব গুলা বিট এক এক করে AND(&) করতে থাকি ডান দিক থেকে তাহলে প্রথম পজিশনের রেজাল্ট হবে 0, তারপর 0, তারপর বাকি দুইটা হবে 1.



আরো সুন্দর মত দেখি,
12 = 1100
13 = 1101
14 = 1110
15 = 1111
------------
(&)= 1100

যদি কোনোভাবে যেকোনো কলামে আমরা দুইটা আলাদা বিট ই (০ এবং ১) পাই তাহলে বাকি সব গুলা কলামের রেজাল্ট হবে শুন্য(০),
কারন ০&১ = ০.

আরো একটা জিনিস খেয়াল করি,সব গুলা নাম্বার এর ডান দিক থেকে যদি বিট বাদ দেয়া শুরু করি, তাহলে আমরা একটা টাইমে খেয়াল করবো, প্রত্যেক্টা নাম্বার সেইম হয়ে গেছে।

১১ থেকে ১৫ এর বাম দিকে দুইটা করে দিট বাদ দিলে বাকি দুইটা করে বিট গুলা সবই সেইম, তাইনা ? তাহলে কিন্তু আমাদেরকে আর একটা রেঞ্জের সব গুলা নাম্বার নিয়ে কাজ করা লাগবে না, শুধুমাত্র প্রথম এবং শেষ নাম্বার নিয়ে কাজ করলেই হচ্ছে।

তাহলে, আমরা একটা লুপ চালাবো যতক্ষন না প্রথম এবং শেষ[A and B] সেইম না হয়, এবং একই সাথে তাদের ডান দিক থেকে বিট বাদ দিতে থাকবো। বাদ দেয়া বিট গুলা AND(&) করলে আমরা শুন্য পাবো, কারন তারা সবাই ভিন্ন ভিন্ন বিট।

বাদ দেয়ার কাজ টা আমরা Right Shift দিয়ে করতে পারি । কোড দেখলে খুব সহজেই বোঝা যাবে।

এখানে লাস্টে আবার কেনো diff_bit দিয়ে Left_shift করলাম ? কারন আমাদেরকে ভিন্ন বিট গুলার জন্য যে কইটা ভিন্ন বিট পাইলাম, সে কইটা শুন্য এড করা লাগবে।