এই সমস্যায়, আমাদের একটি বাইনারি ম্যাট্রিক্স দেওয়া হয়েছে যেখানে প্রতিটি সারির উপাদানগুলি সাজানো হয়েছে। আমাদের কাজ হল সর্বোচ্চ 1 সেকেন্ডের সারি খুঁজে পাওয়া .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
mat[][] = {{ 0 1 1 1}
{1 1 1 1}
{0 0 0 1}
{0 0 1 1}} আউটপুট
1
ব্যাখ্যা
The count of 1’s in each row of the matrix : Row 0 : 3 Row 1 : 4 Row 2 : 1 Row 3 : 2
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রথম 1-এর ক্ষুদ্রতম সূচী সহ সারিটি খুঁজে বের করা।
একটি পদ্ধতি হল প্রথম 1 এর সূচক খুঁজে পেতে সারি অনুসারে ট্রাভার্সাল ব্যবহার করা যা সারিতে সর্বাধিক 1 এর গণনা প্রদান করবে। এবং তারপর আমরা সর্বোচ্চ 1 গণনা সহ সারিটি ফেরত দেব।
আরেকটি পদ্ধতি হল বাইনারী অনুসন্ধান ব্যবহার করা প্রতিটি সারিতে প্রথম 1 এর উপস্থিতি খুঁজে বের করতে। তারপর আমরা সর্বোচ্চ 1 দিয়ে মান ফেরত দেব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findFirst1BinSearch(bool arr[], int low, int high){
if(high >= low){
int mid = low + (high - low)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return findFirst1BinSearch(arr, (mid + 1), high);
else
return findFirst1BinSearch(arr, low, (mid -1));
}
return -1;
}
int findMaxOneRow(bool mat[R][C]){
int max1RowIndex = 0, max = -1;
for (int i = 0; i < R; i++){
int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
if (first1Index != -1 && C-first1Index > max){
max = C - first1Index;
max1RowIndex = i;
}
}
return max1RowIndex;
}
int main(){
bool mat[R][C] = { {0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1}};
cout<<"The row with maximum number of 1's in the matrix is "<<findMaxOneRow(mat);
return 0;
} আউটপুট
The row with maximum number of 1's in the matrix is 1
