শুধুমাত্র 0s এবং 1s সম্বলিত সাজানো সংখ্যার একটি অ্যারে দেওয়া হলে, ট্রানজিশন পয়েন্টটি খুঁজুন। একটি ট্রানজিশন পয়েন্ট হল অ্যারেতে প্রদর্শিত প্রথম '1'-এর সূচক। উদাহরণস্বরূপ,
ইনপুট-1 −
N = 6 arr[ ] = {0,0,0,0,1,1}
আউটপুট −
4
ব্যাখ্যা − যেহেতু 0 এবং 1 সম্বলিত প্রদত্ত অ্যারেতে আমরা দেখতে পাচ্ছি যে সূচক ‘4’-এর উপাদানটির সংখ্যা ‘1’ রয়েছে।
ইনপুট-2 −
N = 5 arr[ ] = {0,0,1,1,1}
আউটপুট −
2
ব্যাখ্যা − 0 এবং 1 সম্বলিত প্রদত্ত অ্যারেতে, আমরা দেখতে পাচ্ছি যে সূচক ‘2’-এর উপাদানটির সংখ্যা ‘1’ রয়েছে। এইভাবে, আমরা 2 ফেরত দেব।
এই সমস্যা সমাধানের পদ্ধতি
প্রদত্ত পূর্ণসংখ্যার বিন্যাসে, আমাদের প্রথম 1 এর সূচী খুঁজে বের করতে হবে। এই বিশেষ সমস্যাটি সমাধান করার জন্য, আমরা প্রথম '1'-এর সূচী খুঁজে বের করার জন্য বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করে এটি সমাধান করতে পারি।
-
এন বাইনারি সংখ্যার একটি অ্যারে ইনপুট নিন
-
এখন একটি ফাংশন ট্রানজিশনপয়েন্ট (int *arr, int n) ইনপুট এবং এর আকার হিসাবে একটি অ্যারে নেয় এবং অ্যারেতে প্রদর্শিত প্রথম '1'-এর সূচী প্রদান করে।
-
দুটি পয়েন্টার নিন কম, উচ্চ যা '0' এবং '1' হিসাবে আরম্ভ করা হয়েছে।
-
এখন আমরা অ্যারের মাঝের বিন্দুটি খুঁজে পাব এবং এটি '1' কিনা তা পরীক্ষা করব।
-
যদি অ্যারের মাঝামাঝি '1' হয় তবে আমরা তার সূচকটি ফেরত দেব অন্যথায় আমরা এগিয়ে গিয়ে পরীক্ষা করব।
-
নিম্ন পয়েন্টার বৃদ্ধি করুন এবং আবার '1' এর জন্য চেক করুন।
-
যতক্ষণ না আমরা '1' না পাই ততক্ষণ ধাপগুলি পুনরাবৃত্তি করুন।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int transitionPoint(int *arr, int n){ int low=0; int high= n-1; while(low<=high){ int mid = (low+high)/2; if(arr[mid]==0) low= mid+1; else if(arr[mid]==1){ if(mid==0 || (mid>0 && arr[mid-1]==0)) return mid; high= mid-1; } } return -1; } int main(){ int n= 6; int arr[n]= {0,0,0,1,1,1}; int ans= transitionPoint(arr,n); if(ans>=0){ cout<<"Transition Point is:"<<ans<<endl; } else{ cout<<"Not Found"<<endl; } return 0; }
আউটপুট
উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
Transition Point is: 3
প্রদত্ত অ্যারে {0,0,0,1,1,1} সূচী '3'-এ উপাদান '1' উপস্থিত রয়েছে, এইভাবে আমরা '3' হিসাবে আউটপুট পাই৷