बाइनरी मैट्रिक्स में पंक्तियों की जोड़ी खोजें जिसमें C++ में अधिकतम बिट अंतर हो

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है; हमें दिए गए मैट्रिक्स में पंक्तियों की जोड़ी ढूंढनी होगी जिसमें अधिकतम बिट अंतर हो।

इसलिए, यदि इनपुट मैट्रिक्स की तरह है, तो आउटपुट [2,3] होगा क्योंकि पंक्तियों 2 और पंक्ति 3 के बीच थोड़ा अंतर 4 है, यह अधिकतम है।

• इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मूल्य और दो बच्चों के साथ ट्री संरचना को परिभाषित करें।

• फ़ंक्शन को परिभाषित करें get_max_bit_diff(), यह एक ट्री, मैट्रिक्स, n, row_index,

  की जड़ लेगा

• अस्थायी:=जड़, गिनती:=0

• इनिशियलाइज़ i :=0 के लिए, जब i

  • यदि अस्थायी का बच्चा [मैट्रिक्स [row_index, i]] NULL नहीं है, तो -

    • अस्थायी:=बच्चे [मैट्रिक्स [row_index, i]] अस्थायी

  • अन्यथा जब अस्थायी का बच्चा [1 - मैट्रिक्स [row_index, i]] NULL नहीं है, तो -

    • अस्थायी:=बच्चे [1- मैट्रिक्स [row_index, i]] अस्थायी

    • (1 से गिनती बढ़ाएं)

• लीफ_इंडेक्स :=तापमान का पत्ता

• temp_count :=0, अस्थायी :=रूट

• इनिशियलाइज़ i :=0 के लिए, जब i

  • यदि बच्चा [1 - मैट्रिक्स [row_index, i]] अस्थायी नहीं है, तो -

    • अस्थायी:=बच्चे [1- मैट्रिक्स [row_index, i]] अस्थायी

    • (temp_count 1 से बढ़ाएं)

  • अन्यथा जब अस्थायी का बच्चा [मैट्रिक्स [row_index, i]] NULL नहीं है, तो -

    • अस्थायी:=बच्चे [मैट्रिक्स [row_index, i]] अस्थायी

• P =अगर temp_count> गिनें तो (temp_count, लीफ ऑफ़ टेम्प) का उपयोग करके एक जोड़ी बनाएं अन्यथा (काउंट, लीफ_इंडेक्स)

  का उपयोग करके एक जोड़ी बनाएं

• वापसी पी

• मुख्य विधि से, निम्न कार्य करें -

• रूट =एक नया TrieNode

• 0वीं पंक्ति को रूट में डालें

• max_bit_diff :=-inf

• एक जोड़ी पीआर और दूसरी जोड़ी अस्थायी परिभाषित करें

• इनिशियलाइज़ i :=1 के लिए, जब i

  • अस्थायी:=get_max_bit_diff (रूट, चटाई, मी, मैं)

  • अगर max_bit_diff <पहले अस्थायी, फिर -

    • max_bit_diff :=temp.first

    • pr :=(temp.second, i + 1)

      . का उपयोग करके एक जोड़ी बनाएं

  • नौवीं पंक्ति को रूट में डालें

• प्रदर्शन जोड़ी पीआर

उदाहरण (C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
class TrieNode {
   public:
   int leaf;
   TrieNode *child[2];
   TrieNode(){
      leaf = 0;
      child[0] = child[1] = NULL;
   }
};
void insert(TrieNode *root, int matrix[][MAX], int n, int row_index){
   TrieNode * temp = root;
   for (int i=0; i<n; i++) {
      if(temp->child[ matrix[row_index][i] ] == NULL)
         temp->child[ matrix[row_index][i] ] = new TrieNode();
         temp = temp->child[ matrix[row_index][i] ];
      }
      temp->leaf = row_index +1 ;
   }
   pair<int, int>get_max_bit_diff(TrieNode * root, int matrix[][MAX], int n, int row_index) {
      TrieNode * temp = root;
      int count = 0;
      for (int i= 0 ; i < n ; i++) {
         if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
         else if (temp->child[1 - matrix[row_index][i]] != NULL) {
            temp = temp->child[1- matrix[row_index][i]];
            count++;
         }
      }
      int leaf_index = temp->leaf;
      int temp_count = 0 ;
      temp = root;
      for (int i= 0 ; i < n ; i++) {
         if (temp->child[ 1 - matrix[row_index][i] ] !=NULL) {
            temp = temp->child[ 1- matrix[row_index][i] ];
            temp_count++;
         }
         else if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
      }
      pair <int ,int> P = temp_count > count ? make_pair(temp_count, temp->leaf): make_pair(count, leaf_index);
      return P;
}
void get_max_diff( int mat[][MAX], int n, int m) {
   TrieNode * root = new TrieNode();
   insert(root, mat, m, 0);
   int max_bit_diff = INT_MIN;
   pair<int ,int> pr, temp ;
   for (int i = 1 ; i < n; i++) {
      temp = get_max_bit_diff(root, mat, m ,i);
      if (max_bit_diff < temp.first ) {
         max_bit_diff = temp.first;
         pr = make_pair( temp.second, i+1);
      }
      insert(root, mat, m, i );
   }
   cout << "(" << pr.first <<", "<< pr.second << ")";
}
int main() {
   int mat[][MAX] = {
      {1 ,1 ,1 ,1 },
      {1, 0, 1 ,1},
      {0 ,1 ,0 ,0},
      {1 ,0 ,0 ,0}
   };
   get_max_diff(mat, 4, 4) ;
}

इनपुट

{{1 ,1 ,1 ,1 },
{1, 0, 1 ,1},
{0 ,1 ,0 ,0},
{1 ,0 ,0 ,0}}, 4,4

आउटपुट

(2,3)