मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है; हमें दी गई मैट्रिक्स में पंक्तियों का वह जोड़ा ढूंढना है जिसमें अधिकतम बिट अंतर हो।
तो, यदि इनपुट मैट्रिक्स जैसा है, तो आउटपुट [2,3] होगा क्योंकि पंक्ति 2 और पंक्ति 3 के बीच बिट अंतर 4 है, जो अधिकतम है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
ट्राई संरचना को परिभाषित करें, जिसमें मान और दो बच्चे हों।
एक फ़ंक्शन get_max_bit_diff() परिभाषित करें, यह ट्राई के रूट, मैट्रिक्स, n, row_index लेगा,
temp := रूट, काउंट := 0
i := 0 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
यदि temp का child[ matrix[row_index, i] ] NULL नहीं है, तो -
temp := temp का child[ matrix[row_index, i] ]
अन्यथा जब temp का child[1 - matrix[row_index, i]] NULL नहीं है, तो -
temp := temp का child[1- matrix[row_index, i]]
(काउंट को 1 से बढ़ाएं)
leaf_index := temp का लीफ
temp_count := 0, temp := रूट
i := 0 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
यदि temp का child[ 1 - matrix[row_index, i] ] NULL नहीं है, तो -
temp := temp का child[ 1- matrix[row_index, i] ]
(temp_count को 1 से बढ़ाएं)
अन्यथा जब temp का child[ matrix[row_index, i] ] NULL नहीं है, तो -
temp := temp का child[ matrix[row_index, i] ]
P = यदि temp_count > काउंट तो (temp_count, temp का लीफ) का उपयोग करके एक जोड़ी बनाएं अन्यथा (काउंट, leaf_index) का उपयोग करके एक जोड़ी बनाएं
P लौटाएं
मुख्य विधि से, निम्नलिखित करें -
रूट = एक नया TrieNode
0वीं पंक्ति को रूट में डालें
max_bit_diff := -inf
एक जोड़ी pr और दूसरी जोड़ी temp परिभाषित करें
i := 1 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
temp := get_max_bit_diff(root, mat, m, i)
यदि max_bit_diff < temp का पहला, तो -
max_bit_diff := temp.first
pr := (temp.second, i + 1) का उपयोग करके एक जोड़ी बनाएं
iवीं पंक्ति को रूट में डालें
जोड़ी pr प्रदर्शित करें
उदाहरण (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)
