একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে। যেই দুটি সারির মধ্যে বিট পার্থক্য (Hamming distance) সর্বোচ্চ সেটি বের করতে হবে। ট্রাই (Trie) ডেটা স্ট্রাকচার ব্যবহার করে O(N×M) তে সমাধান করা যায়।
অ্যালগরিদম
- প্রথম সারিটি ট্রাইতে ইনসার্ট করুন।
- পরবর্তী প্রতিটি সারির জন্য ট্রাইতে ট্রাভার্স করে সর্বোচ্চ বিট পার্থক্য বের করুন।
- প בבিটে যদি বিপরীত বিটের চাইল্ড থাকে, সেখানে যান (পার্থক্য বাড়াবে)। নাই তবে সেম বিটের চাইল্ডে যান।
- সারিটি ইনসার্ট করুন এবং সর্বোচ্চ পার্থক্য ও সারির ইন্ডেক্স আপডেট করুন।
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 mat[][MAX], int m, int row) {
TrieNode* temp = root;
for (int i = 0; i < m; i++) {
int bit = mat[row][i];
if (!temp->child[bit]) temp->child[bit] = new TrieNode();
temp = temp->child[bit];
}
temp->leaf = row + 1;
}
pair<int,int> getMaxBitDiff(TrieNode* root, int mat[][MAX], int m, int row) {
TrieNode* temp = root;
int count = 0;
for (int i = 0; i < m; i++) {
int bit = mat[row][i];
if (temp->child[bit]) temp = temp->child[bit];
else if (temp->child[1-bit]) { temp = temp->child[1-bit]; count++; }
}
int leaf_idx = temp->leaf;
int temp_count = 0; temp = root;
for (int i = 0; i < m; i++) {
int bit = mat[row][i];
if (temp->child[1-bit]) { temp = temp->child[1-bit]; temp_count++; }
else if (temp->child[bit]) temp = temp->child[bit];
}
return (temp_count > count) ? make_pair(temp_count, temp->leaf) : make_pair(count, leaf_idx);
}
void getMaxDiff(int mat[][MAX], int n, int m) {
TrieNode* root = new TrieNode();
insert(root, mat, m, 0);
int maxDiff = INT_MIN;
pair<int,int> pr, tmp;
for (int i = 1; i < n; i++) {
tmp = getMaxBitDiff(root, mat, m, i);
if (tmp.first > maxDiff) {
maxDiff = tmp.first;
pr = {tmp.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}};
getMaxDiff(mat, 4, 4);
return 0;
}
আউটপুট: (2, 3)
