Calculate Summation of GCD(i,n); for i = 1 to n

আমাদের এবারের কাজ হল ১ থেকে n পর্যন্ত সবগুলো সংখ্যার সাথে n এর গ.সা.গু. বের করে তাদের যোগফল বের করা।
শুনতে ব্যাপারটি সহজ মনে হলেও, আসলে ঠিক সহজ না, যদি না আমরা সঠিক এপ্রোচ না জানি। নরমালি আমরা যখন প্রোগ্রামিং এ নতুন, তখন আমরা ১ থেকে n পর্যন্ত লুপ চালায়ে তাদের যোগফল বের করতাম।


এখন কথা হচ্ছে, এভাবে করলে আমরা বড় বড় সংখ্যার জন্য আমরা TLE খাবো। যেমন n = 1000000000 এর জন্য আমাদের প্রচুর সময় লাগবে, ( ইচ্ছে করলে উপরের কোডটি নিজ দায়িত্বে রান করে দেখে নিতে পারো :3 )

এখন তাহলে আমরা কিভাবে এর সমাধান করবো? খেয়াল করলে দেখবো যে, আমরা যখন ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যাগুলোর সাথে n এর গসাগু বের করার চেষ্টা করছি,তখন আসলে আমরা প্রতিবার n এর সবগুলো বিভাজক( all divisor ; there maybe multiple occurance of divisors) নিয়ে তাদের যোগফলটা নিচ্ছি। যেমনঃ  n = 8 হলে, gcd(1,8) + gcd(2,8) + gcd(3,8) + gcd(4,8) + gcd(5,8) + gcd(6,8) + gcd(7,8) + gcd(8,8)  = 1+2+1+4+1+2+1+8 = 20।
এখানে খেয়াল করে দেখি যে, আমরা কিন্তু ১,২,৪,৮ ছাড়া আর কিছু যোগ করছিনা! আর এই সংখ্যাগুলি কিন্তু আসলে ৮ এর বিভাজক (divisor)। আমরা আপাতত গোনায় বাদ রাখলাম কোন সংখ্যা কতবার নিচ্ছি, কিন্তু আসল কথা হচ্ছে আমরা n এর divosr গুলিকেই নিচ্ছি আমাদের ক্যাল্কুলেশন এর জন্য। তাহলে বুঝা যাচ্ছে আমাদের আসলে n এর divisor গুলি বের করতে হবে। আর আমরা O(√n) কমপ্লেক্সিটি তে n এর divisor বের করতে পারি। কাজেই, n = 1000000000 এর জন্য আমরা 31622.77.. কমপ্লেক্সিটিতে divisor গুলি বের করে, এরপরে আমাদের বাকি কাজ করবো।

তাহলে  n = 8 এর জন্য, আমাদের যোগফল অনেকটা এরকম হবে দেখতেঃ

\sum _{ i=1 }^{ 8 }{ gcd(i,n) } = coef1*(1)+coef2*(2)+coef3*(4)+coef4*(8)

এখানে coef1,coef2… এগুলোই আমাদের বের করতে হবে। divisor গুলি আমরা আগেই পেয়ে গেছি।
১ থেকে n পর্যন্ত সংখ্যাগুলোর সাথে n এর গ.সা.গু. বের করতে গেলে,গ.সা.গু = ১ কতবার আসবে, সেই সংখ্যাটা আসলে n এর অয়লার ফাংশন। অয়লার ফাংশন সম্পর্কে না জানলে এই লিঙ্ক দেখার অনুরোধ রইল আগে।
আচ্ছে এখান থেকে আমরা একটু মনযোগ দেয়ার চেষ্টা করি, 

phi (8) = 4.
phi (4) = 2.

phi (2) = 1.
phi (1) = 1.
আমরা এখানে আসলে ৮ এর divisor গুলির phi এর মান দেখলাম।
আচ্ছে এখন দেখা যাক, phi(8) = 4 এর জন্য, কোন কোন জোড়া নিলে আমাদের গসাগু ১ আসছেঃ
(1,8), (3,8), (5,8), (7,8); কাজেই, আমাদের coef1 = 4 হবে। ( coef1*(1); এই 1 এর মানে হচ্ছে, ঐসব জোড়া আমরা নিবো, যাদের মাঝের গ.সা.গু. = 1 হবে, এরকম জোড়া আছে 4 টি, কাজেই আমাদের coef1 = 4 )
এখন আমরা বের করবো coef2 এর মান। কাজেই আমাদের বের করতে হবে এমন কতটি জোড়া আছে, যারা 8 এর সাথে গ.সা.গু.  = 2 হবে। এজন্য আমাদের দরকার phi(8/2) = phi(4) এর মান। আমরা আগেই বের করে রেখেছি, phi(4) = 2. কাজেই আমাদের coef2 = 2. একইভাবে, coef3,coef4 বের করতে পারবো আমরা। ফাইনালি,

coef1 = phi(8/1) = phi(8) = 4. ; divide by first divisor = 1.
coef2 = phi(8/2) = phi(4) = 2. ; divide by second divisor = 2.
coef3 = phi(8/4) = phi(2) = 1. ; divide by third divisor = 4.
coef4 = phi(8/8) = phi(1) = 1. ; divide by forth divisor = 8.

কাজেই, আমাদের ফাইনাল রেজাল্ট ঃ
phi(8/1)*1 + phi(8/2)*2 + phi(8/4)*4 + phi(8/8)*8
= 4*1 + 2*2 + 1*4 + 1*8 = 20
 

অ্যালগরিদম (Algorithm)

without pre computing phi values:


এখন আমাদের অনেক কুয়েরি থাকলে আমাদের আগে থেকে phi এর মান বের করে রাখতে হবে। ঐ ব্যাপারটা তোমরা নিজেরা করে দেখো। আবার যদি আমাদের n এর মান অনেক বড় হয়ে যায় যে, আমরা O(√n) এও TLE খাচ্ছি, তাহলে আমাদের number theorem এর অন্যরকম এপ্রোচ নিতে হবে। এগুলো নিয়ে পরে আলোচনা করা যাবে। 

Advertisements

Euler’s Totient or Phi Function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর  সহমৌলিক (relative prime). অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন সাধারন উৎপাদক (common divisor) নেই, আরেকটু সহজ করে বলতে গেলেঃ 1 থেকে N এর মাঝে, যাদের সাথে N এর GCD = 1. উদাহরন :
15 সংখ্যাটি বিবেচনা করি,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এর মধ্যে থেকে 15 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে মার্ক করিঃ
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

এই সংখ্যাগুলিকে বাদ দিবো, কেননা 15 এর গুননীয়ক ঃ 3 এবং 5. কাজেই, এদের গুনিতক (3, 5, 6, 9, 10, 12, 15) এগুলো বাদ যাবে।
তাহলে অবশিষ্ট থাকে টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
সুতরাং, φ( 15 ) = 8.

এখন চিন্তা করি, মৌলিক সংখ্যার জন্য phi এর মান কত হবে?
খেয়াল করলে দেখবো যে, আসলে কোন মৌলিক সংখ্যার সাথে তার আগের সকল সংখ্যাই সহমৌলিক, অর্থাৎ এদের মাঝে ১ ছাড়া আর কোন গুননীয়ক নেই। অর্থাৎ, φ(প্রাইম) = প্রাইম – ১

7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1, 2, 3, 4, 5, 6, 7
so, φ(7) = 7-1 = 6.
so, φ(prime) = prime-1

মৌলিক সংখ্যার ক্ষেত্রে কাজটা অনেক সহজ হলেও অন্যান্য ক্ষেত্রে কিছুটা জটিল। এজন্য আমাদের একটি Theorem জানতে হবে। সেটি হলঃ

φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime

এর জন্য, আমাদের i এবং j, উভয়কেই সহমৌলিক হতে হবে। এখন খেয়াল করি, আমরা যদি, i এবং j কে এমনভাবে নিয়ে আসতে পারি, যে তারা উভয়েই প্রাইম হবে, অর্থাৎ যেকোন সংখ্যাকে আমরা প্রাইম এর ফ্যাক্টরে নিয়ে আসতে যদি পারি, তাহলে আমাদের জন্য φ(prime) = prime-1 দিয়ে প্রতি প্রাইম ফ্যাক্টর এর phi বের করা খুবি সহজ, এবং সেখান থেকে φ( i*j ) = φ( i ) * φ( j ) এই ফর্মুলার মাধ্যমে আমরা প্রাইম ফ্যাক্টর থেকে প্রাপ্ত phi এর মান গুন করে দিলেই মূল সংখ্যার phi এর মান পেয়ে যাবো। উদাহরনঃ

φ( 30 ) = φ( 2 ) * φ( 3 ) * φ( 5 )
now, φ( 2 ) = 1, φ( 3 ) = 2, φ( 5 ) = 4.
so, φ( 30 ) = 1 * 2 * 4 = 8

অর্থাৎ 1 থেকে 30 এর মাঝে, 30 এর সাথে সহমৌলিক 8 টি সংখ্যা আছে।
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
এগুলো হলঃ 1, 7, 11, 13, 17, 19, 23, 29 (Total 8 numbers).

এখন ধরা যাক, আমরা 4-এর φ ফাংশনের মান বের করতে চাই। আমরা এখন পর্যন্ত যা জানি, তা অনুযায়ী,

 φ(4) = φ(2)*φ(2) = 1*1 = 1.

কিন্তু ,
GCD(1,4) = 1, রিলেটিভলি প্রাইম
GCD(2,4) = 2
GCD(3,4) = 1, রিলেটিভলি প্রাইম
GCD(4,4) = 4
অর্থাৎ, φ(4) = 2

এটি কিন্তু আমাদের ফর্মুলা অনুযায়ী মিলেনি। তাহলে আমরা এখান থেকে একটি জিনিস খেয়াল করতে পারি যে, যখন আমাদের প্রাইম ফ্যাক্টরের ঘাত (power) ১ হবে, কেবলমাত্র তখনি আমরা আমাদের উপোরক্ত ফর্মুলা ব্যবহার করতে পারবো। তাহলে এরকম ক্ষেত্রে আমাদের ফর্মুলার একটু পরিবর্তন আসবে এভাবে ঃ
φ( n) = n– nk-1 , when n is prime and k != 1.

তাহলে আমরা এতক্ষনের আলোচনা থেকে ৩ টি গুরুত্বপূর্ণ ব্যাপার দেখলাম। এগুলি হলঃ 

  1. φ( n ) = n – 1, when is prime and power is 1.
  2. φ( n) = n– nk-1 ,when n is prime and k != 1.
  3. φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime.

অ্যালগরিদম (Algorithm)

আমরা 1 থেকে N পর্যন্ত লুপ চালায়ে ব্রূট ফোর্স অ্যালগরিদম লিখতে পারি এভাবেঃ

কিন্তু এটি বড় বড় সংখ্যার জন্য রান করতে অনেক সময় নিবে, কাজেই এটি তেমন ভালো এপ্রোচ না আমাদের জন্য।
এবার আমরা একটু অন্যভাবে প্রোগ্রাম করবো।

৩৬ = (২*২)*(৩*৩)
φ(৩৬) এর সর্বোচ্চ মান হতে পারে ৩৬। কাজেই আমরা ইনিশিয়ালি, result = 36 লিখে রাখবো।
এর মৌলিক গুণনীয়ক আছে দুইটিঃ ২ এবং ৩। এখন,
১ থেকে ৩৬-এর মধ্যে ২-এর গুণনীয়ক কয়টি আছে?  উত্তরঃ ৩৬/২ = ১৮ টি।
তাহলে, আমরা লিখবো result = result – 18 = 36 – 18 = 18.

এখন আমরা ৩৬ কে ২ দিয়ে যতবার ভাগ করা যায়, করে ফেলবো। এক্ষেত্রে ২ বার ভাগ করার পরে আমরা পাবো ৯।
এখন ১ থেকে ১৮ এর মাঝে ৩ এর গুণনীয়ক আছে , ১৮/৩ = ৬ টি।
তাহলে আমরা লিখবো result = result – 6 = 18 – 6 = 12.
সুতরাং, φ(৩৬) = ১২।

এরপরে আমরা আবার ৯ কে ৩ দিয়ে ভাগ করতে থাকবো। যদি আমাদের n এর মান ১ হয়ে যায়, তাহলে আমাদের আর কিছু করার দরকার নাই। কিন্তু যদি ১ না হয়, তাহলে আমরা result = result – result/n করবো, কেননা, ১ যেহেতু হয়নি, কাজেই, n আসলে প্রাইম নাম্বার ছিল। আর আমরা আগেই জানি, প্রাইম এর জন্য φ(prime) = prime-1

এতক্ষন আমরা যেসব phi জেনারেট করলাম, তার সবই সিম্পল কুয়েরির ক্ষেত্রে ভালো এবং দ্রুত আউটপুট দিবে, কিন্তু, আমাদের যদি কুয়েরির মান অনেক হয়, তাহলে বারবার phi ফাংশন কল করলে আমাদের প্রোগ্রাম TLE দিবে। এজন্য আমাদের আরও এফিশিয়েন্ট অ্যালগরিদম দরকার, যার মাধ্যমে আমরা সহজে অনেকগুলি phi এর মান আগে থেকে জেনারেট করে এরপরে কুয়েরির অ্যান্সার করবো। ঠিক সীভ (sieve of eratosthenes) যেভাবে জেনারেট করতাম, সেভাবে জেনারেট করবো। সকলের জন্য পরামর্শ রইল নিজে কোডটি লিখার। চেষ্টা করার পরে না পারলে এরপরে নিচের কোড দেখে শিখে নেয়া যাবে।

ফাইনালি, একটি সুন্দর জিনিস দেখা যাক।
For any integer n, the sum of the totient(phi) values of each of its divisors equals n”.

এখন দেখা যাকঃ
n = summation of φ( x ) ; where x are the divisors of n.
যেমন, 30 এর divisor = 

1 x 30
2 x 15
3 x 10
5 x 6
so,  30 = φ( 1 )+φ( 2 )+φ( 3 )+φ( 5 )+φ( 6 )+φ( 10 )+φ( 15 )+φ( 30 ) = 1+1+2+4+2+4+8+8 = 30
অর্থাত, যেকোন সংখ্যার সকল divisor এর phi এর মানের যোগফল, ঐ সংখ্যার সমান হবে।

Practice Problems

 

Set

সেট (Set)

সেট বলতে আমরা ইউনিক জিনিস বুঝে থাকি। যেমন আমার কাছে অনেকগুলি চকলেট আছে, ২ টি মার্স, ১০ টি স্নিকার্স, ৭ টি কিটক্যাট, ১৮ টি সাফারী। এখন আমি যদি আমার চকলেট এর সেট করতে চাই, তাহলে
s = { Mars, Snikers, Kitkat, Safari };
এখানে কিন্তু কোন চকলেট কতবার আছে তা জানার কোন দরকার নেই। আমার খালি দরকার আমার কাছে ইউনিক কি আছে। সেট এই কাজটা করে। STL এর সেট ভ্যালুগুলিকে ইউনিক আকার এবং একই সাথে সর্টেড আকারেও রাখে।
#include <set>
int main(){
set < int > s;
s.insert ( 10 );
s.insert ( 10 );
s.insert ( 1 );
s.insert ( 10 );
s.insert ( 10 );
s.insert ( 2 );
s.insert ( 2 );
set < int > :: iterator it; // সেট এর ভ্যালু পয়েন্ট করার জন্য ইটারেটর ডিক্লার
for ( it = s.begin(); it != s.end(); it++ )
cout << *it << endl;  // সেট এর ভ্যালুগুলি প্রিন্ট করলাম
cout << s.size() << endl; //সেট এর সাইজ প্রিন্ট করলাম
}
ধরি আমাকে অনেকগুলি নম্বর দেয়া হল। আমাকে বলতে হবে এর মধ্যে ইউনিক কতটি নম্বর আছে। এর জন্য আমরা খালি সেট এর মধ্যে ইনসার্ট করতে থাকবো এবং সেট এর সাইজটি প্রিন্ট করে দিবো।

Upper_Bound & Lower_Bound

আপার_বাউন্ড এবং লোয়ার_বাউন্ড(upper_bound & lower_bound)

আপার_বাউন্ড এবং লোয়ার_বাউন্ড খুব গুরুত্বপুর্ণ  একটি টপিক। এখন একটি কাহিনী দেখা যাকঃ
আসিফ এবং আসফি ২ যমজ ভাই। তাদের বয়স ধরি ২১। অর্থাৎ তাদের বিয়ের বয়স হয়েছে। তারা আবার খুব হ্যান্ডসাম এবং একই সাথে ব্রিলিয়ান্ট এবং তাদের আগে কোন ফুল-গার্লফ্রেন্ড, হাফ-গার্লফ্রেন্ড কিছুই ছিলনা। কাজেই তাদের বিয়ে করার কথা শুনে মেয়েরা পাগলপ্রায়। এখন আসিফ এর পছন্দ তার থেকে কম বা তার সমান বয়স্ক মেয়েদের (বউ হিসেবে)। অন্যদিকে আসফি এর পছন্দ তার থেকে বেশি বয়স্ক মেয়েদের। এখন ধরি প্রায় ১০০ জন মেয়ে তাদেরকে বিয়ে করার জন্য আগ্রহী। আমাদের কাজ হবে আসিফ এবং আসফি এর জন্য সঠিক বয়সের পাত্রী খুঁজে বের করা। কিভাবে করবো কাজটা? প্রথমেই আমরা পাত্রীদের কে তাদের বয়সের ক্রমানুসারে কম থেকে বেশি আকারে সাজাই। এই সংখ্যাগুলি ধরে একটি ভেক্টর এর মধ্যে রাখি। ধরি আমাদের ভেক্টরটি দেখতে এরকমঃ
int v [ ] = { 10, 12, 14, 21, 21, 21, 21, 30, 32 };
এখন আমরা এই v ভেক্টর এর উপর লোয়ার_বাউন্ড চালালে পাবো ২১, যা ৩ তম ইনডেক্স। আর আপার_বাউন্ড চালালে পাবো ৩০, যা ২১ থেকে ঠিক বড়।

Output :
lower_bound at position 3
upper_bound at position 6
upper_bound & lower_bound ফাংশন এর জন্য সি++ এর হেডার ফাইল ব্যবহার করা হয়।
ভেক্টর এর ইনিশিয়াল এবং এনডিং অ্যাড্রেস এবং কোন ভ্যালুর সাপেক্ষে আমরা বাউন্ড বের করতে চাই এগুলি প্যারামিটার হিসেবে দিতে হবে।

Iterator

ইটারেটর(Iterator)

ইটারেটর আসলে সি এর পয়েন্টার এর মত কাজ করে। পয়েন্টার একটি অ্যাড্রেসকে পয়েন্ট করে থাকে যা থেকে আমরা পরবর্তীতে সেই অ্যাড্রেস এর ডাটা নিয়ে কাজ করতে পারি। সি++ এর ইটারেটর এর কাজ ও ঠিক ওরকম। STL ফাংশনগুলি অনেক ক্ষেত্রে অ্যাড্রেস পাঠায় আমরা যে ডাটাকে খুঁজছি, তা কোথায় আছে তার। ইটারেটর ডিক্লার করে এভাবে–>
vector< int > :: iterator it ;
আমরা ভেক্টর এর একটি ইটারেটর it ডিক্লার করলাম।
এখন ভেক্টর এর সব এলেমেন্ট দেখতে চাইলে আমরা এটা করবো–>
for ( it = v.begin(); it != v.end(); it++ )   // v নামের একটি ইন্টিজার এর ভেক্টর নিলাম।
       cout << *it << endl;  // *it দিয়ে আমরা it অ্যাড্রেস যাকে পয়েন্ট করে আছে, তার ভ্যালু প্রিন্ট করলাম।

Searching Algo

লিনিয়ার সার্চ(Linear Search)

লিনিয়ার সার্চ সবচেয়ে ব্যাসিক সার্চ টেকনিক। ধরি আমাদের n টি নম্বর এর একটি অ্যাারে দেয়া আছে। এখন আরেকটি নম্বর a দিয়ে আমাকে জিজ্ঞাসা করা হল, এই a , আগের n টি নম্বর এর মাঝে আছে কিনা। স্বাভাবিকভাবে আমরা 0 থেকে n (অ্যাারে এর ঘর বিবেচনা করলে) পর্যন্ত একটি লুপ চালায়ে নম্বরটিকে বের করার চেষ্টা করবো।

int arr [ ] = { 1, 2, 4, 12, 14, 78, 21, -90, 111, 1467};
int a = 111;
for ( int i = 0; i < 10; i++ ){
          if ( arr [ i ] == a ){
                cout << ” Found the number 😀 ” << endl;
                break;
}
}
সার্চিং এর ক্ষেত্রে লিনিয়ার সার্চ ছোট রেঞ্জ এর মধ্যে কাজ করবে কিন্তু রেঞ্জ বড় হয়ে গেলে TLE দিবে। আমরা লিনিয়ারি একটি পজিশন থেকে আরেকটি পজিশন এ যাচ্ছি ( n তম এলেমেন্ট পাওয়ার জন্য আমাদের শুরু থেকে n পর্যন্ত যেতে হবে), কাজেই লিনিয়ার সার্চের কমপ্লেক্সিটি O ( n )  [ Order of n ] যেখানে n হল কতটি এলেমেন্ট এর মাঝে সার্চিংটি চলছে।

বাইনারি সার্চ(Binary Search)

বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ টেকনিক এবং এর ব্যবহার ও খুব মজার। বাইনারি সার্চের জন্য প্রথমেই আমাদের নম্বরগুলিকে কোন একটি অর্ডার এ সাজাতে হবে ( Ascending or Descending )। এরপরে আমরা ২টি পজিশন সেট করবো low এবং high নামে। low  হবে আমাদের অ্যাারে এর 0th ইনডেক্স এবং high হবে (n-1)th ইনডেক্স। এখন আমরা এই high এবং low এর মাঝে থেকে middle ইনডেক্স বের করার চেষ্টা করবো এবং চেক করবো ঐ middle ইনডেক্স এর ভ্যালুটা আমাদের কাঙ্ক্ষিত ভ্যালুর সাথে মিলে গেছে কিনা। যদি মিলে যায়, তাহলে আমরা আমাদের ভ্যালু পেয়ে গেছি। যদি না মিলে, তবে ২টি কন্ডিশন হতে পারে।
১ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে বড়।
২ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে ছোট।
ধরি আমাদের অ্যাারেটি ছোট থেকে বড় আকারে সাজানো আছে। এখন ১ এর জন্য মিড ভ্যালুটি বড়, কাজেই আমাদের কাঙ্ক্ষিত ভ্যালুটি মিড ইনডেক্স এর অবশ্যই আগে আছে। কাজেই তখন আমাদের high হয়ে যাবে middle – 1 এবং low এর কোন চেঞ্জ হবেনা। ২ঃ এর খেত্রেও একই ব্যাপার। তখন low হবে middle + 1 এবং high এর কোন চেঞ্জ হবেনা। একটি উদাহরন দেখিঃ আমাদের ২০ কে খুঁজে বের করতে হবে। binary-search
টাইম কমপ্লেক্সিটি ঃ আমরা প্রতিবার সার্চিং এর জন্য একটি অংশ নিচ্ছি এবং অন্যটি বাদ দিয়ে দিচ্ছি। কাজেই worst case এর জন্য আমাদের কমপ্লেক্সিটি হবে O ( N * logN )।
স্যাম্পল কোড ঃ Capture
আমরা ভ্যালু পেয়ে গেলে ভ্যালুটির ইনডেক্স রিটার্ন করবো, আর না পেলে -1 রিটার্ন করবো। লক্ষ্য করলে দেখবে যে বাইনারি সার্চ এর টারমিনেট কন্ডিশন যখন high এর চেয়ে low এর ইনডেক্স বড় হয়ে যাবে। এই ব্যাপারগুলি ভালোভাবে খেয়াল না রাখলে ইনফিনিট লুপ এ পরবে প্রোগ্রাম। কোড করার সময় তাই আমাদের মাথায় রাখতে হবে আসলে কখন কোথায় কি হচ্ছে এবং কখন কোন কন্ডিশন দিলে ঠিকমতন প্রোগ্রাম রান করবে।

 

Priority Queue

প্রায়োরিটি কিউ (Priority Queue)

ঠিক কিউ এর মতই, তবে এর একটি সুন্দর দিক হচ্ছে এটি প্রোগ্রামারের প্রায়োরিটি অনুযায়ী কাজ করে।
ধরি কোন একটি জিনিস নিলামের জন্য ডাকা হল। এখন ক্রেতা অনেক। একেকজন একেক দাম হাঁকছে। ধরলাম ক্রেতা আবির, কালাম, হাসান, মমতাজ যথাক্রমে ১০, ৩০, ১২, ১৪ টাকা দাম ডাকলো। এখন আবির আগে ১০ টাকা ডাকলেও, কালাম কিন্তু ৩০ টাকা ডাকার কারনে তার প্রায়োরিটি বেশি হবে বিক্রেতার কাছে। তাই বিক্রেতা চাবে কালামকে জিনিসটি দিতে। এরপরে কালাম চলে গেলে বেশি প্রায়োরিটি পাবে মমতাজ। প্রায়োরিটি কিউ ঠিক এরকম বিক্রেতার মত আচরন করে। default প্রায়োরিটি কিউ বড় থেকে ছোট ভ্যালু প্রসেস করে। কাজেই এক্ষেত্রে ৩০, ১৪, ১২, ১০ এভাবে ভ্যালুগুলি সাজানো থাকবে কিউতে।
Captureএখন আমরা যদি ছোট থেকে বড় প্রায়োরিটি অনুসারে সাজাতে চাই? তাহলে ব্যাপারটা কি হবে? একটি হিনটস দেইঃ আমরা ইনসার্ট এর সময় ভ্যালুগুলিকে মাইনাস ১ ( -1 ) দিয়ে গুন করে ইনসার্ট করতে পারি। এছাড়াও সর্টিং, কমপ্যারিং এর আরো কিছু মেথড আছে, সেগুলা আমরা পরে অন্য কোন জায়গায় আলোচনা করবো।