इस समस्या में, हमें एक बाइनरी मैट्रिक्स दिया जाता है जिसमें प्रत्येक पंक्ति को क्रमबद्ध किया जाता है। हमारा कार्य एक बाइनरी मैट्रिक्स की पंक्ति संख्या ज्ञात करना है जिसकी अधिकतम संख्या 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 से अधिक है तो बाइनरी खोज करें लेकिन अंतिम पंक्ति में 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