এই সমস্যায়, আমাদের একটি বাইনারি অ্যারে বিন [] দেওয়া হয়েছে যা শুধুমাত্র 0 এবং 1 এর সমন্বয়ে গঠিত। আমাদের কাজ হল শূন্যের সংখ্যা বের করা .
অ্যারেটি সাজানো হয়েছে অর্থাৎ 1 এর পরে সমস্ত 0 একসাথে সাজানো হয়েছে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {1, 1, 1, 0, 0, 0, 0} আউটপুট
4
সমাধান পদ্ধতি
সমস্যাটির একটি সহজ সমাধান হল অ্যারেটি সাজানো, অর্থাৎ অ্যারের 0 এর সংখ্যাটি অ্যারেতে 0 এর প্রথম উপস্থিতি ব্যবহার করে পাওয়া যেতে পারে। প্রথম ঘটনার পরে সমস্ত মান শূন্য হবে।
অ্যারেতে 0 এর প্রথম উপস্থিতি খোঁজার জন্য। আমরা সার্চিং অ্যালগরিদম ব্যবহার করতে পারি।
লিনিয়ার সার্চ − প্রথম 0-এর জন্য রৈখিক অনুসন্ধানে, আমরা পুরো অ্যারেটি অতিক্রম করব যতক্ষণ না প্রথম 0 সম্মুখীন না হয় তারপর আমরা অ্যারের প্রথম ঘটনা এবং আকার ব্যবহার করে গণনা ফেরত দেব। এই সমাধানটি ব্যবহার করে আমরা সমস্যার সময় জটিলতা তৈরি করি O(N).
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findFirstZero(int arr[], int n){
for(int i = 0; i < n; i++){
if(arr[i] == 0){
return i;
}
}
return -1;
}
int countZerosArr(int arr[], int n){
int firstOccZero = findFirstZero(arr, n);
if (firstOccZero == -1)
return 0;
return (n - firstOccZero);
}
int main(){
int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The count of zeros in array is "<<countZerosArr(arr, n);
return 0;
} আউটপুট
The count of zeros in array is 5
বাইনারি অনুসন্ধান − বাইনারি অনুসন্ধানে, মাঝখানের উপাদানটি 1 বা 0 কিনা তার উপর ভিত্তি করে অ্যারের বিভাগটিকে ভাগ করে আমরা প্রথম 0 খুঁজে পাব। এবং 0-এর প্রথম উপস্থিতির সূচকটি ফেরত দেব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findFirstZero(int arr[], int start, int end){
if (end >= start){
int mid = start + (end - start) / 2;
if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
return mid;
if (arr[mid] == 1)
return findFirstZero(arr, (mid + 1), end);
else
return findFirstZero(arr, start, (mid -1));
}
return -1;
}
int countZerosArr(int arr[], int n){
int firstOccZero = findFirstZero(arr, 0, n - 1);
if (firstOccZero == -1)
return 0;
return (n - firstOccZero);
}
int main(){
int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The count of zeros in array is "<<countZerosArr(arr, n);
return 0;
} আউটপুট
The count of zeros in array is 7
