इस समस्या में, हमें एक बाइनरी मैट्रिक्स दिया जाता है जहां प्रत्येक पंक्ति के तत्वों को क्रमबद्ध किया जाता है। हमारा काम है अधिकतम 1s वाली पंक्ति ढूँढना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
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
