এই সমস্যাতে, আমাদের একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে যেটির প্রতিটি সারির এলিমেন্টগুলো সর্টেড। আমাদের কাজ হল সর্বাধিক ১ থাকা সারি বের করা।
উদাহরণ দেখি:
ইনপুট
mat[][] = {{ 0 1 1 1} {1 1 1 1} {0 0 0 1} {0 0 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
