এই সমস্যায়, আমাদের একটি বাইনারি ম্যাট্রিক্স দেওয়া হয়েছে যাতে প্রতিটি সারি সাজানো হয়। আমাদের কাজ হল বাইনারি ম্যাট্রিক্সের সারি নম্বর খুঁজে বের করা যার সর্বোচ্চ সংখ্যা 1s।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
binMat[][] = {
1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 1
} আউটপুট
1
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রতিটি সারিতে মোট 1 এর সংখ্যা গণনা করা। এবং তারপর সর্বাধিক 1 গণনা সহ সারি নম্বরটি ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
int oneCount = 0;
for(int j = 0; j < C; j++){
if(mat[i][j])
oneCount++;
}
if(oneCount > max1Count){
max1Count = oneCount;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} আউটপুট
সারির সংখ্যা সর্বাধিক 1 এর সংখ্যা 1 হল সমস্যার একটি ভাল সমাধান হল প্রতিটি সারিতে বাইনারি অনুসন্ধান ব্যবহার করে সারিতে 1 এর প্রথম ঘটনাটি খুঁজে বের করা। সারির 1 নম্বরটি সারির আকার - প্রথম 1-এর সূচী ব্যবহার করে পাওয়া যেতে পারে। এটি ব্যবহার করে, আমরা প্রতিটি সারিতে 1 এর সংখ্যা খুঁজে পেতে পারি এবং তারপর সর্বাধিক সংখ্যা 1 এর সাথে সারিটি ফেরত দিতে পারি
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
index = binarySearch1Row(mat[i], 0, C-1);
if (index != -1 && ( C-index) > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} আউটপুট
The number of row with maximum number of 1's is 1
উপরের পদ্ধতিতে যোগ করা একটি অপ্টিমাইজেশান প্রথম 1 এর সূচী ব্যবহার করে বর্তমান সারিতে আগের সারির চেয়ে বেশি 1 আছে কিনা তা পরীক্ষা করা যেতে পারে। যদি 1 এর বেশি থাকে তবে বাইনারি অনুসন্ধান করুন তবে শেষ সারিতে 0 থেকে প্রথম 1 এর সূচক পর্যন্ত।
এটি বর্তমানের চেয়ে কম 1 এর সাথে একটি সারিতে 1 এর সংখ্যা গণনা করার ওভারহেডগুলি সংরক্ষণ করবে৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int i, index;
int max1Row = 0;
int max1Count = binarySearch1Row(mat[0], 0, C - 1);
for (i = 1; i < R; i++){
if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) {
index = binarySearch1Row (mat[i], 0, C - max1Count);
if (index != -1 && C - index > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
else
max1Count = binarySearch1Row(mat[i], 0, C - 1);
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
} আউটপুট
The number of row with maximum number of 1's is 1
