সি++-এ বাইনারি ম্যাট্রিক্সে সর্বোচ্চ ১ वाली সারির নম্বর বের করা

এই সমস্যাতে, আমাদের একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে যেখানে প্রতিটি সারি সর্টেড (sorted)। আমাদের কাজ হলো বাইনারি ম্যাট্রিক্সে সর্বোচ্চ ১ वाली সারির নম্বর বের করা।

উদাহরণ দিয়ে সমস্যা বোঝা যাক,

ইনপুট

binMat[][] = {
    1, 1, 1, 1
    0, 0, 0, 0
    0, 0, 0, 1
    0, 0, 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;
}

আউটপুট

The number of row with maximum number of 1's is 1

এই সমস্যার একটি উন্নত সমাধান হলো প্রতিটি সারিতে বাইনারি সার্চ (binary search) ব্যবহার করে প্রথম ১-এর ইনডেক্স বের করা। সারিতে ১-র সংখ্যা = সারির সাইজ - প্রথম ১-এর ইনডেক্স। এই পদ্ধতিতে প্রতিটি সারিতে ১-র সংখ্যা বের করে সর্বোচ্চ ১ वाली সারি রিটার্ন করা যায়।

সমাধান কোড (বাইনারি সার্চ):

উদাহরণ

#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

উপরোক্ত পদ্ধতিতে একটি অপ্টিমাইজেশন যোগ করা যায়: চেক করা যে বর্তমান সারিতে আগের সারির চেয়ে বেশি ১ আছে কিনা প্রথম ১-এর ইনডেক্স ব্যবহার করে। যদি বেশি থাকে তবে বাইনারি সার্চ করব কিন্তু ০ থেকে আগের সারির প্রথম ১-এর ইনডেক্স পর্যন্ত। এটি কম ১ वाली সারির ১-র সংখ্যা গণনার ওভারহেড বাঁচাবে।

অপ্টিমাইজড সমাধান কোড:

উদাহরণ

#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