শুধুমাত্র 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' হিসাবে আউটপুট পাই৷
