C++ में क्रमबद्ध मैट्रिक्स में x से छोटे या बराबर तत्वों की गिनती

समस्या विवरण

हमें n x n आकार का एक मैट्रिक्स, एक पूर्णांक x दिया गया है। मैट्रिक्स के तत्व क्रमबद्ध (sorted) क्रम में रखे गए हैं। हमें उन तत्वों की गिनती करनी है जो x से छोटे या बराबर हैं।

उदाहरण

इनपुट

matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, X = 4

आउटपुट

गिनती = 4

व्याख्या

x=4 से छोटे या बराबर तत्व: 1, 2, 3, 4।

समाधान दृष्टिकोण

चूंकि मैट्रिक्स क्रमबद्ध है, हम प्रत्येक पंक्ति को पार करके गिन सकते हैं। सरल दृष्टिकोण: सभी तत्वों को जांचें और गिनें। अनुकूलित दृष्टिकोण: प्रत्येक पंक्ति के लिए बाइनरी सर्च या सीढ़ीनुमा खोज (staircase search) का उपयोग करें।

कार्यकारी प्रोग्राम (सरल दृष्टिकोण)

#include <bits/stdc++.h>
using namespace std;

#define SIZE 3

int countElements(int matrix[SIZE][SIZE], int x) {
    int count = 0;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (matrix[i][j] <= x) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int matrix[SIZE][SIZE] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int x = 5;
    cout << "x से छोटे या बराबर तत्वों की गिनती: " << countElements(matrix, x);
    return 0;
}

आउटपुट

x से छोटे या बराबर तत्वों की गिनती: 5