কোন অ্যারেতে (সর্টেড) সাধারনত জোড়ায় জোড়ায় ভ্যালু খুঁজে বের করার একটি এফিশিয়েন্ট টেকনিক হল ২-পয়েন্টার। আমরা মূলত, কোন সর্টেড অ্যারেতে ২ বা তার বেশি জোড় বের করবো এমনভাবে, যেন তারা কোন কন্ডিশন মেনে চলে। যেমনঃ এমন ১ জোড়া ভ্যালু বের কর যাদের যোগফল X এর সমান হয়, অথবা বিয়োগফল, বা গুনফল ইত্যাদি।
প্রথমে একটি প্রবলেম নিয়ে আলোচনা করা যাক। আমাদের একটি সর্টেড (ছোট থেকে বড়) অ্যারে দেয়া আছে। এখান থেকে এমন একটি জোড়া বের করতে হবে, যাতে তাদের যোগফল X এর সমান হয়। এবং জোড়ার ২ টির ইন্ডেক্স একই হওয়া যাবেনা। আমরা কোড করলে অনেকটা এভাবে ২ টি লুপ চালায়ে করে ফেলবোঃ
এর কপ্লেক্সিটি O(n*(n-1)) যা অনেক বেশি। আমাদের আরও ভালো এপ্রোচ লাগবে। এখন দেখা যাক এই প্রব্লেমটার জন্য ২-পয়েন্টার কিভাবে কাজ করবেঃপ্রথমে একটি প্রবলেম নিয়ে আলোচনা করা যাক। আমাদের একটি সর্টেড (ছোট থেকে বড়) অ্যারে দেয়া আছে। এখান থেকে এমন একটি জোড়া বের করতে হবে, যাতে তাদের যোগফল X এর সমান হয়। এবং জোড়ার ২ টির ইন্ডেক্স একই হওয়া যাবেনা। আমরা কোড করলে অনেকটা এভাবে ২ টি লুপ চালায়ে করে ফেলবোঃ
আমরা প্রথমে ২ টি পয়েন্টার সেট করবো। একটি হবে প্রথম ভ্যালুর জন্য, অপরটি হবে দ্বিতীয় ভ্যালুর জন্য। আমরা প্রত্যেকবার চেক করবো X এর সাথে ভ্যালু ২ টির যোগফল মিলে যাচ্ছে কিনা। যদি যোগফল X এর চেয়ে কম হয়, তাহলে আমরা প্রথম পয়েন্টারকে ডানদিকে বাড়াবো। যদি যোগফল X এর চেয়ে বেশি হয়, তাহলে আমরা দ্বিতীয় পয়েন্টারকে বামদিকে কমাবো। অনেকটা বাইনারি সার্চ এর মত কাজ করবে এই ২- পয়েন্টার। এবং আমাদের কন্ডিশন অনুযায়ী প্রথম এবং দ্বিতীয় ভ্যালুর ইনডেক্স সেইম হওয়া যাবেনা। ২ পয়েন্টার এর প্রথমটিকে আমরা 0 (এখানে অ্যারের প্রথম ইনডেক্স 0 ধরে ) এবং পরের পয়েন্টারকে আমরা অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ
১ম প্রব্লেম
২ টি সর্টেড অ্যারে(ভিন্ন ভিন্ন সাইজ) থেকে আমাদের এমন ২ টি এলেমেন্ট নিতে হবে (প্রত্যেক অ্যারে থেকে ১ টি), যাতে তাদের যোগফল X এর সমান বা ছোট (ম্যাক্সিমাম যোগফল, অর্থাৎ X এর কাছাকাছি হয়)।
আমরা প্রথম অ্যারেতে একটি পয়েন্টার এবং দ্বিতীয় অ্যারেতে আরেকটি পয়েন্টার সেট করবো। এখন প্রতিবার আমরা চেক করবো X এর সমান অথবা আমাদের ম্যাক্সিমাম সাম X এর কাছাকাছি কিনা, যদি না হয়, আমরা ইনডেক্স আপডেট করবো। এখন যদি সাম X এর চেয়ে কম হয়, তাহলে আমরা প্রথম অ্যারের ইনডেক্স বাড়াবো, নাহলে দ্বিতীয় অ্যারের ইনডেক্স বাড়াবো। এখানে প্রথম পয়েন্টারকে অ্যারের প্রথম ইনডেক্স এবং পরের পয়েন্টারকে অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ
২য় প্রব্লেম
একটি ভিন্ন ভিন্ন (distinct) এলেমেন্ট এর অ্যারে থেকে এমন একটি ট্রিপলেট (তিন টি এলেমেনট এর জোড়া) বের করতে হবে, যাদের যোগফল শুন্য হবে।
২ জোড়ার জন্য আমরা যেভাবে করতাম, এটাও একইভাবে হবে, খালি এক্সট্রা একটি ভ্যালুর জন্য আমরা আগেই একটি ভ্যালু নিয়ে নিব। প্রথমে অ্যারেকে সর্ট করে ফেলবো। এরপরে আমরা আগের মতন যেভাবে জোড়া বের করতাম, একইভাবে এখানেও সেই কাজ করবো। এখানে আমরা একটি ইনডেক্স কে ফিক্সড করে, বাকি ইনডেক্স এর মাঝে ২ টি পয়েন্টার ঠিক আগের মতন করে সেট করবো। কোড দেখা যাকঃ
৩য় প্রব্লেম
আমাদের যদি কোন ট্রিপলেট বের করতে বলে, যাদের যোগফল X এর সমান হবে, আমরা সেইম উপরের টেকনিক অনুযায়ী বের করে ফেলতে পারবো।
৪র্থ প্রব্লেম
এমন ট্রিপলেট বের কর, যাতে যেকোন ২ টির যোগফল, তৃতীয় টির সমান হবে।
এই সমস্যাটিও হুবহু আগের মতই কাজ করবে। আমরা প্রথমে একটি এলেমেন্টকে সেট করবো, এরপরে বাকি ২ টি এলেমেন্ট বের করবো যাতে তাদের সাম, সেট করা এলেমেন্ট এর সমান হয়। কোডঃ
এই সমস্যাটিও হুবহু আগের মতই কাজ করবে। আমরা প্রথমে একটি এলেমেন্টকে সেট করবো, এরপরে বাকি ২ টি এলেমেন্ট বের করবো যাতে তাদের সাম, সেট করা এলেমেন্ট এর সমান হয়। কোডঃ
২ - পয়েন্টারের প্রব্লেমগুলিতে আমরা ইনডেক্স কে একেকভাবে সেট করতে পারি, এটা আসলে যে কোড লিখছে তার উপর নির্ভর করে। তবে মূল আইডিয়া ঠিক থাকলে প্রব্লেম এর ফাইনাল আউটপুট সবসময় একই আসবে।
No comments:
Post a Comment