একটি বাইনারি ম্যাট্রিক্সে সারিগুলির জোড়া খুঁজুন যেখানে C++ এ সর্বাধিক বিট পার্থক্য রয়েছে

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে; আমাদের প্রদত্ত ম্যাট্রিক্সে সারিগুলির জোড়া খুঁজে বের করতে হবে যার সর্বাধিক বিট পার্থক্য রয়েছে।

সুতরাং, যদি ইনপুটটি ম্যাট্রিক্সের মতো হয়, তাহলে আউটপুট হবে [2,3] কারণ সারি 2 এবং সারি 3 এর মধ্যে বিট পার্থক্য 4, এটি সর্বাধিক।

• এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• মান এবং দুটি সন্তান সহ Trie গঠন সংজ্ঞায়িত করুন।

• একটি ফাংশন get_max_bit_diff() সংজ্ঞায়িত করুন, এটি একটি trie, matrix, n, row_index,

  রুট করবে

• temp :=root, count :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি চাইল্ড[ ম্যাট্রিক্স[রো_ইনডেক্স, i] ] এর তাপমাত্রা NULL না হয়, তাহলে -

    • temp :=চাইল্ড[ ম্যাট্রিক্স[row_index, i] ] temp

  • অন্যথায় যখন চাইল্ড[1 - ম্যাট্রিক্স[রো_ইনডেক্স, i]] এর তাপমাত্রা NULL না হয়, তাহলে −

    • temp :=চাইল্ড[1- ম্যাট্রিক্স[row_index, i]] temp

    • (গণনা 1 দ্বারা বৃদ্ধি করুন)

• leaf_index :=তাপমাত্রার পাতা

• temp_count :=0, temp :=root

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি শিশু [ 1 - ম্যাট্রিক্স [ row_index , i ] ] temp এর মান NULL না হয়, তাহলে -

    • temp :=শিশু[ 1- ম্যাট্রিক্স[row_index, i] ] temp

    • (temp_count 1 দ্বারা বৃদ্ধি করুন)

  • অন্যথায় যখন টেম্পের চাইল্ড[ ম্যাট্রিক্স[রো_ইনডেক্স, i] ] NULL হয় না, তখন -

    • temp :=চাইল্ড[ ম্যাট্রিক্স[row_index, i] ] temp

• P =যদি temp_count> গণনা হয় তাহলে (temp_count, টেম্পের পাতা) ব্যবহার করে একটি জোড়া তৈরি করুন অন্যথায় (count, leaf_index) ব্যবহার করে একটি জোড়া তৈরি করুন

• ফেরত P

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• root =একটি নতুন TrieNode

• রুটে 0ম সারি ঢোকান

• max_bit_diff :=-inf

• এক জোড়া pr এবং অন্য জোড়া temp

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=1, যখন i

  • temp :=get_max_bit_diff(root, mat, m, i)

  • যদি max_bit_diff

    • max_bit_diff :=temp.first

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

      ব্যবহার করে একটি জোড়া তৈরি করুন

  • রুট এ সারি ঢোকান

• প্রদর্শন জোড়া pr

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#includeনেমস্পেস ব্যবহার করে std;const int MAX =100;class TrieNode { public:int leaf; TrieNode *শিশু[2]; TrieNode(){ পাতা =0; শিশু[0] =শিশু[1] =NULL; }};অকার্যকর সন্নিবেশ(TrieNode *root, int matrix[][MAX], int n, int row_index){ TrieNode * temp =root; (int i=0; ichild[ matrix[row_index][i] ] ==NULL) temp->child[ matrix[row_index][i] ] =new TrieNode( ); temp =temp->শিশু[ ম্যাট্রিক্স[রো_ইনডেক্স][i] ]; } temp->পাতা =সারি_সূচক +1; } pairget_max_bit_diff(TrieNode * root, int matrix[][MAX], int n, int row_index) { TrieNode * temp =root; int count =0; (int i=0; i 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]]; গণনা++; } } int leaf_index =temp-> পাতা; int temp_count =0; temp =root; (int i=0; i child[ 1 - matrix[row_index][i] ] !=NULL) { temp =temp->child[ 1- matrix[row_index][ i]]; temp_count++; } অন্যথায় যদি (temp->child[ matrix[row_index][i] ] !=NULL) temp =temp->child[ matrix[row_index][i] ]; } জোড়া  P =temp_count> count? make_pair(temp_count, temp->leaf):make_pair(count, leaf_index); রিটার্ন P;}void get_max_diff(int mat[][MAX], int n, int m) { TrieNode * root =new TrieNode(); সন্নিবেশ (মূল, মাদুর, মি, 0); int max_bit_diff =INT_MIN; pair pr, temp; জন্য (int i =1; i  
ইনপুট
 <প্রে>{{1 ,1 ,1 ,1 },{1, 0, 1 ,1},{0 ,1 ,0 ,0},{1 ,0 ,0 ,0}}, 4,4 
আউটপুট
 
(2,3)