এই সমস্যাতে, আমাদের একটি বাইনারি অ্যারে bin[] দেওয়া আছে যেটি শুধু ০ এবং ১ দিয়ে গঠিত। আমাদের কাজ হল শূন্যের সংখ্যা বের করা।
অ্যারেটি সর্টেড অর্থাৎ সব ১ গুলো আগে এবং তারপর সব ০ গুলো থাকে।
উদাহরণ দেখি:
ইনপুট
arr[] = {1, 1, 1, 0, 0, 0, 0}
আউটপুট
4
সমাধানের পদ্ধতি
অ্যারেটি সর্টেড থাকায় ০-এর সংখ্যা বের করা সহজ - প্রথম ০-এর অকারেন্স বের করলেই বাকিগুলো ০ হবে। প্রথম ০ খুঁজে বের করার জন্য সার্চিং অ্যালগরিদম ব্যবহার করা যায়।
লিনিয়ার সার্চ - প্রথম ০ খুঁজে বের করলে ইনডেক্স এবং অ্যারে সাইজ দিয়ে কাউন্ট রিটার্ন করা। টাইম কমপ্লেক্সিটি 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
বাইনারি সার্চ - মিড এলিমেন্ট ১ নাকি ০ চেক করে অ্যারের সেকশন ভাগ করে প্রথম ০ খুঁজে বের করা।
উদাহরণ
#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
