pow(a, n) – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১

সমস্যাঃ একটি ফাংশন তৈরি করতে হবে, যেখানে দুটি ইন্টিজার (a, n) ইনপুট দেওয়া থাকলে ফাংশনটি a^n রিটার্ন করবে। ফাংশনটির রানটাইম হতে হবে O(log n)।

সমাধানঃ আমাদেরকে যেটি করতে হবে, সেটি হচ্ছে pow() ফাংশনটি ইমপ্লিমেন্ট করতে হবে। কিন্তু এতে ঘাবড়াবার কিছু নেই। আমরা পাইথনে খুব সহজে এটি ইমপ্লিমেন্ট করতে পারি।

def pow(a, n):
   result = 1.0
   for _ in range(n):
      result = result * a
   return result

ওপরে যেই ফাংশনটি লিখলাম, সেটির কমপ্লেক্সিটি কত? টাইম কমপ্লেক্সিটি হচ্ছে O(n)। কিন্তু আমাদেরকে বলা হয়েছে O(log n) কমপ্লেক্সিটিতে ইমপ্লিমেন্ট করতে। যদি এটি বলা না থাকতো, তাহলে কিন্তু ওপরের কোড লিখে দিলেই হতো।
আমরা ডিভাইড এন্ড কনকোয়ার পদ্ধতিতে সমস্যাটির সমাধান করতে পারি। সেজন্য আমাদেরকে একটি বিষয় উপলব্ধি করতে হবে। a^n-কে আমরা লিখতে পারি, (a^n/2) * (a^n/2). যেমন, 5^4 হচ্ছে 625. কিন্তু আমরা 5^4-কে লিখতে পারি, (5^2) * (5^2)। এভাবে লিখে লাভ কী হলো? লাভ হচ্ছে, 5^2 এর মান আমাদের দুবার বের করতে হবে না, একবার বের করলেই হবে। কিংবা ধরা যাক, আমাদেরকে 2^32-এর মান বের করতে বলা হলো।

2^32 = (2^16) * (2^16)
2^16 = (2^8) * (2^8)
2^8 = (2^4) * (2^4)
2^4 = (2^2) * (2^2)
2^2 = (2^1) * (2^1)

এখন আমরা জানি, a^0 হচ্ছে 1 আর a^1 হচ্ছে a. তাই রিকার্শন ব্যবহার করে সমস্যাটির সমাধান বের করতে কিন্তু আমাদের তেমন বেগ পেতে হবে না। আর n যদি জোড় সংখ্যা না হয়ে বিজোড় সংখ্যা হতো, তখন আমাদের কী করতে হবে? তখন a^n-কে আমরা লিখতে পারি a^(n-1) * a. n যেহেতু বিজোড় সংখ্যা, n-1 অবশ্যই জোড় সংখ্যা। তাই আমরা আবার আগের মতো আগাতে পারি।

এখন আমি প্রোগ্রাম লিখে ফেলি –

def pow(a, n):
   if n == 0: return 1
   if n == 1: return a 

   if n % 2 == 1:
      return a * pow(a, n-1) 
   else:
      p = pow(a, n/2)
      return p * p

ওপরের pow() ফাংশনটির কমপ্লেক্সিটি হচ্ছে O(log n)। কেন সেটি আর এখানে বিস্তারিত ব্যাখ্যা করলাম না, তবে যারা বাইনারি সার্চের কমপ্লেক্সিটি বোঝে, তাদের এটি বুঝতে কোনো সমস্যা হবে না।

সমস্যাটির সমাধান কিন্তু পুরোপুরি হয় নি। কারণ n যদি ঋণাত্মক হয় তখন কিন্তু প্রোগ্রামটি কাজ করবে না। এটি ঠিকঠাক করার জন্য আমাদেরকে কী করতে হবে?

Facebook Comments

Leave a Reply