এই সমস্যায়, আমাদেরকে সাজানো ক্রমে বুলিয়ান মান (শুধুমাত্র 0 এবং 1 এর) সমন্বিত একটি অসীম অ্যারে বিন [] দেওয়া হয়েছে। আমাদের কাজ হল 0 এবং 1 এর অসীম সাজানো অ্যারেতে প্রথম 1-এর সূচক খুঁজে পাওয়া .
এখানে, আমাদের একটি অসীম অ্যারে রয়েছে যা গ্যারান্টি দেয় যে অ্যারের মধ্যে 1টি বিদ্যমান।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : bin[] = {0, 0, 0, 1, 1, ....}
Output : 3 ব্যাখ্যা −
First 1 of the binary array is encountered at index 3.
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের মূলত অ্যারেতে 1ম 1 এর সূচকটি খুঁজে বের করতে হবে। এর জন্য আমরা একটি অনুসন্ধান কৌশল ব্যবহার করতে পারি।
একটি পদ্ধতি রৈখিক অনুসন্ধান ব্যবহার করা যেতে পারে, আমরা একটি অসীম লুপ ব্যবহার করে অ্যারে অতিক্রম করব। এবং অ্যারের প্রথম 1-এর সূচী ফেরত দিন, অন্যথায় -1 প্রিন্ট করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[]) {
int i = 0;
while(1){
if (bin[i] == 1)
return i;
i++;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1 };
cout<<"The index of 1st occurrence of 1 in infinite array is "<<find1stOneInfiniteArray(bin);
return 0;
} আউটপুট
The index of 1st occurrence of 1 in infinite array is 3
অন্য একটি অনুসন্ধান কৌশল যেটি ব্যবহার করা যেতে পারে বাইনারি অনুসন্ধান হিসাবে অ্যারে সাজানো হয়।
শুধুমাত্র আমাদের অ্যালগরিদম আপডেট করতে হবে কারণ কোনো উপরের সীমা নেই, আমরা সূচক মান 1 থেকে প্রথম 1-এর সংঘটনের সূচকে উচ্চ মান দ্বিগুণ করে এটি খুঁজে পাব।
এই সীমাগুলি ব্যবহার করে, আমরা বাইনারি অনুসন্ধান ব্যবহার করে সূচকটি খুঁজে পেতে পারি।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[], int low, int high) {
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
return mid;
else if (bin[mid] == 1)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
int low = 0;
int high = 1;
while(bin[high] != 1){
low = high;
high *= 2;
}
cout<<"The index of 1st occurrence of 1 in infinite array is " <<find1stOneInfiniteArray(bin,low, high);
return 0;
} আউটপুট
The index of 1st occurrence of 1 in infinite array is 3
