পর্ব - ২ (সমস্যা - ১)

আমরা একটি ইনপুট নিবো , বলতে হবে ইনপুট নাম্বারটিকে 2 এর Power হিসেবে লিখা যায় কি যায় না ।

Naive Solution হতে পারে , নাম্বারটিকে 2 দিয়ে ভাগ করতে থাকবো যতক্ষণ 2 দিয়ে ভাগ যায় । এভাবে ভাগ করতে করতে যদি নাম্বারটিকে 1 বানানো  যায় তাহলে আমরা বলতে পারবো যে নাম্বারটিকে 2 এর Power হিসেবে লিখা যায়।

যেমন ঃ 16 = 2⁴

16/2 = 8

8/2 = 4

4/2 = 2

2/2 = 1

# Naive Solution





এই প্রোগ্রামের কমপ্লেক্সিটি  O(logN) ।

কিন্তু বিট Manipulation এর মাধ্যমে এটি Constant time অর্থাৎ O(1) কমপ্লেক্সিটিতে বের করা যায় ।
8 এর বাইনারি {1000}₂ এবং 8 কে 2 এর Power হিসেবে লিখা যায় ( 2³) । 7 এর বাইনারি {111}₂ । তাহলে 7 ও 8 এর মধ্যে & Operation করলে {1000}₂   & {0111}₂ = 0 । অর্থাৎ শুধুমাত্র যেসব নাম্বার কে 2 এর Power হিসেবে লিখা যায় সেসব নাম্বার  এবং তার immediate আগের নাম্বারটির মধ্যে & Operation করলে Result সবসময় 0 - ই হবে কেননা 2 এর Power হিসেবে লিখা যায় এমন নাম্বার  এবং তার immediate আগের নাম্বারটির মধ্যকার সব বাইনারি বিট ভিন্ন বিধায় তাদের মধ্যে & Operation করলে Result 0 - ই হবে ।

# Solution with বিট Manipulation




# Code Analysis

2 এর Power হিসেবে লিখা যায় এসব নাম্বারের ক্ষেত্রে (n & (n-1)) এর মান 0 , তাহলে !(n & (n-1)) এর মান 1 । এর সাথে n কে logical and (&&) দিয়ে যুক্ত করা হয়েছে , এটি শুধু n শূন্য ব্যতিত সব নাম্বারের ক্ষেত্রে সত্য অর্থাৎ 0 কে 2 এর Power হিসেবে লিখা যায় না দেখেই এভাবে !(n & (n-1)) এর সাথে n কে logical and দিয়ে যুক্ত করা হয়েছে ।