Two Pointer [ Lec – 2.1 ]

আমরা প্রত্যেকেই ছোটবেলায় একটা গল্প শুনেছি অথবা পড়েছি । দুই ইঁদুর আর এক বানরের । গল্পটা অনেকটা এইরকম যতদূর মনে পড়ে –

দুই বানর একটা রুটি চুরি করে । এখন দুইজনে সমান দুই ভাগ করে যে রুটিটা খাবে সেটা আর পারছে না । তাদের পাশ দিয়ে হঠাৎ করে একটা বানর যাচ্ছিল । তারা ঠিক করলো বানরকে দিয়ে রুটিটা দুই ভাগ করাবে ।  বানর খুশি খুশিই রাজী হয়ে গেলো । প্রথমে রুটিটাকে দুই ভাগ করলো এরপর দেখলো একপাশে একটু বেশি আছে । সেইপাশ থেকে অল্প একটু ছিড়ে খেয়ে ফেললো । এরপর দেখলো আরেক পাশের রুটি এখন একটু বেশি মনে হচ্ছে । এরপর সেই অংশ থেকে রুটি একটু ছিড়ে খেয়ে ফেললো ।

যাদের গল্পের বাকি অংশ জানার ইচ্ছা গুগল করে জেনে নিয়ো 😛 । আমার যতটুকু প্রয়োজন ততোটুকু বলে ফেলেছি ।

জিনিসটা হচ্ছে ব্যালেন্সিং করা । কোন পাশে কমে গেলে আরেক পাশ থেকে একটু কমিয়ে আনা । বা কোন অংশে বেড়ে গেলে আরেক পাশকে বাড়ানোর চেষ্টা করা । যেমন বাজারে ১ কেজি চাল কিনতে গেলে প্রথমে পাল্লার এক পাশে এক কেজির বাটখাড়া রাখা হয় এরপর অন্য পাশে চাল ওজন করা হয় । প্রয়োজনের চেয়ে বেশি চাল উঠলে কমানো হয় আবার কম উঠলে আরো কিছু চাল এনে দেয়া হয় ।

“ টু পয়েন্টার ” হলো একটা টেকনিক । সাধারণত একটি বিশেষ জোড়া বের করার জন্য ব্যবহৃত হয় ।

 

উদাহরণ দিয়ে একটু বুঝার চেষ্টা করি ।

4 এর সমান অথবা 4  হতে বড় যেকোন সংখ্যাকে দু’টি প্রাইম নাম্বারের যোগফল রূপে প্রকাশ করা সম্ভব ।

4 = 2 + 2

5 = 2 + 3

6 = 3 +3

7 = 2 + 5

8 = 3 + 5

9 = 2 + 7

10 = (3+7)/(5 + 5)

আমাকে যদি কোন নাম্বার দিয়ে বলা হয় যে সেই নাম্বারকে দু’টি প্রাইম নাম্বারের যোগফল রূপে দেখাতে (উপরের উদাহরণের মতো ) সেক্ষেত্রে আমরা Two Pointer টেকনিক ব্যবহার করতে পারি ।

[ এখানে প্রাইম নাম্বার নিয়ে চিন্তা করাটা মূল ব্যাপার না । মূল ব্যাপার হচ্ছে এই যোগফলটা কিভাবে বের করা সম্ভব ]

Two pointer টেকনিক ব্যবহার করার আগে এরেকে(যেখান থেকে আমি কোন তথ্য চাচ্ছি । উপরের উদাহরনে যেমন প্রাইম নাম্বারের একটা এরে থেকে) সেটা সোর্টেড হতে হবে । নাহলে কমানো বা বাড়ানোর কাজটা ঠিক করা যাবে না ।

উপরের প্রবলেমের কোডটা নিচে দেয়া হলো ।

TwoPointer

এখানে primeNum এর একটা এরে নিলাম আমরা প্রথমে (যেখানে সবকয়টা প্রাইম নাম্বার রাখা)। এরপর ইউজারের কাছ থেকে একটা ইনপুট নিবো যেটাকে আমার দু’টো প্রাইম নাম্বারের সমষ্টি রূপে দেখাতে হবে ।

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

এবার আমার দুইটা পয়েন্টার লাগবে । যে জিনিস দিয়ে আমি ওজন (এক্ষেত্রে যোগফল) বাড়ানো কমানোর কাজটা করবো ।

left এবং right দুইটা ভেরিয়েবল নিলাম । left এর ভ্যালু 0 অর্থাৎ সবচেয়ে ছোট প্রাইম নাম্বারকে যে পয়েন্ট করে থাকবে । আর right এর ভ্যালু 9 (length or size of the array)  সবচেয়ে বড় প্রাইম নাম্বারটাকে পয়েন্ট করে থাকবে ।

এই ভেরিয়েবল দুটি আদতে এরের index এর ভ্যালু হোল্ড করে । যেটাকে আমরা বলছি এরেতে ছোট কিংবা বড় ভ্যালুকে পয়েন্ট করে থাকে .

এরপরেই একটা লুপ চালাচ্ছি যতক্ষণ পর্যন্ত left  এর মান right এর ছোট থাকবে অথবা সমান হবে ততক্ষণ পর্যন্ত লুপটা চালিয়ে আমি আমার কাঙ্ক্ষিত প্রাইম যুগল বের করার চেষ্টা করবো ।

একটা ইনপুটের জন্য লুপটা চালিয়ে দেখি . ধরলাম ইনপুট 10

১ম বার =>

left = 0, right = 9

sum = primeNum[0] + primeNum[9]  = 2 + 29 = 31

এই ৩১ ভ্যালুটা কি আমার কাঙ্ক্ষিত ভ্যালু ১০ এর সমান ? না , তাহলে  বড় না ছোট ?

১০ থেকে ৩১ বড় ।

তাহলে আমাকে এমনকিছু করতে হবে যেন পরেরবার ভ্যালুটা ১০ এর কাছাকাছি যায় । মানে ৩১ এর থেকে কম আসে । আমার right পয়েন্ট করে আছে সবচেয়ে বড় ভ্যালুকে আর let ছোট ভ্যালুকে । দুইটার যোগফল ছোট করার জন্য আমাড় কি করা দরকার ? right এখন যাকে পয়েন্ট করে আছে তার চেয়ে ছোট ভ্যালুকে যেন এরপরেরবার পয়েন্ট করে । সুতরাং right — । right এর ভ্যালু এক কমে 8 এখন ।

২য় বার =>

left = 0, right = 8

sum = primeNum[0] + primeNum[8]  = 2 + 23 = 25

এইবারও যোগফল ১০ এর থেকে বেশি right এর মান আবার কমাবো right– . right = 7 .

৩য় বার =>

left = 0, right = 7

sum = primeNum[0] + primeNum[7]  = 2 + 19 = 21

এইবারও যোগফল ১০ এর থেকে বেশি right এর মান আবার কমাবো right– . right = 6 .

৪র্থ বার =>

left = 0, right = 6

sum = primeNum[0] + primeNum[6]  = 2 + 17 = 19

এইবারও যোগফল ১০ এর থেকে বেশি right এর মান আবার কমাবো right– . right = 5 .

৫ম বার =>

left = 0, right = 5

sum = primeNum[0] + primeNum[5]  = 2 + 13 = 15

এইবারও যোগফল ১০ এর থেকে বেশি right এর মান আবার কমাবো right– . right = 4 .

৬ষ্ঠ বার =>

left = 0, right = 4

sum = primeNum[0] + primeNum[4]  = 2 + 11 = 13

এইবারও যোগফল ১০ এর থেকে বেশি right এর মান আবার কমাবো right– . right = 3 .

 

৭ম বার =>

left = 0, right = 3

sum = primeNum[0] + primeNum[4]  = 2 + 7 = 9

এইবার কিন্তু যোগফল ১০ এর থেকে ছোট হয়ে গেলো । এখন এমন কিছু করতে হবে যেন যোগফলটা বাড়ে । যেহেতু যোগফলটা ১০ এর চেয়ে ছোট । এই বাড়ানোর জন্য আমার এখন সবচেয়ে ছোট ভ্যালুটা চেঞ্জ করতে হবে । সুতরাং left এখন যাকে পয়েন্ট করে আছে পরে যেন তার থেকে বড় কাউকে পয়েন্ট করে । left++ . left = 1 হয়ে গেলো এখন

৮ম বার =>

left = 1, right = 3

sum = primeNum[1] + primeNum[4]  = 3 + 7 =  10

টাডা , 10 পেয়ে গেলাম । এবার যেহেতু আমার কাঙ্ক্ষিত নাম্বার পেয়ে গেছি । লুপ ব্রেক করে বাহিরে চলে আসছি আমি ।

আর left আর right এর কাছে যেহেতু এরের ইন্ডেক্সের মান আছে সেহেতু পরে তা সরাসরি প্রিন্ট করে দিচ্ছি । আউটপুট দেখতে অনেকটা এই রকম হবে ।

output

[ উদাহরণে লুপের কন্ডিশনটা আলাদা করে চেক করে অহেতুক লিখা বড় করা হয় নি । যেহেতু লুপ চলছে প্রতিবারই কিন্তু কন্ডিশন চেক হচ্ছে । আর left কিন্তু সবসময়ই right এর থেকে ছোট ছিল ]

Practice Problem:

11057 – Exact Sum

543 – Goldbach’s Conjecture (এইটা সলভ করার জন্য আগে প্রাইম নাম্বার জেনারেট করা শিখতে হবে)

Advertisements

2 thoughts on “Two Pointer [ Lec – 2.1 ]

    1. সময়ের উপর নির্ভর করে । চেষ্টা করবো ।
      লিখা পড়ার জন্য ধন্যবাদ 🙂

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s