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