Given a Binary Matrix. The task is to find the pair of row in the Binary matrix that has maximum bit difference Examples:
Input: mat[][] = {{1, 1, 1, 1},
{1, 1, 0, 1},
{0, 0, 0, 0}};
Output : (1, 3)
Bit difference between row numbers 1 and 3
is maximum with value 4. Bit difference
between 1 and 2 is 1 and between 2 and 3
is 3.
Input: mat[][] = {{1 ,1 ,1 ,1 }
{1 ,0, 1 ,1 }
{0 ,1 ,0 ,0 }
{0, 0 ,0 ,0 }}
Output : (2, 3)
Bit difference between rows 2 and 3 is
maximum which is 4.
Input: mat[][] = {{1 ,0 ,1 ,1 }
{1 ,1 ,1 ,1 }
{0 ,1 ,0 ,1 }
{1, 0 ,0 ,0 }}
Output : (1, 3) or (2 ,4 ) or (3 ,4 )
They all are having maximum bit difference
that is 3
Simple solution of this problem is that pick each row of binary matrix one -by -one and compute maximum bit difference with rest of the rows of matrix .at last return rows those have maximum bit difference .
An Efficient solution using Trie Data Structure. Below is algorithm.
1). Create an empty Trie. Every node of Trie contains
two children for 0 and 1 bits.
2). Insert First Row of Binary matrix into Trie
3).Traverse rest of the rows of given Binary Matrix
a). For Each Row First we search maximum bit difference
with rows that we insert before that in Trie and
count bit difference
b). For every search we update maximum bit_diff count
if needed else not store pair of index that have
maximum bit difference
c). At Last Print Pair
Implementation:
CPP
// C++ program to Find Pair of row in Binary matrix// that has maximum Bit difference#include<bits/stdc++.h>using namespace std;// Maximum size of matrixconst int MAX = 100;struct TrieNode{ int leaf; //store index of visited row struct TrieNode *Child[2];};// Utility function to create a new Trie nodeTrieNode * getNode(){ TrieNode * newNode = new TrieNode; newNode->leaf = 0; newNode->Child[0] = newNode->Child[1] = NULL; return newNode;}// utility function insert new row in trievoid insert(TrieNode *root, int Mat[][MAX], int n, int row_index){ TrieNode * temp = root; for (int i=0; i<n; i++) { // Add a new Node into trie if(temp->Child[ Mat[row_index][i] ] == NULL) temp->Child[ Mat[row_index][i] ] = getNode(); // move current node to point next node in trie temp = temp->Child[ Mat[row_index][i] ]; } // store index of currently inserted row temp->leaf = row_index +1 ;}// utility function calculate maximum bit difference of// current row with previous visited row of binary matrixpair<int, int> maxBitDiffCount(TrieNode * root, int Mat[][MAX], int n, int row_index){ TrieNode * temp = root; int count = 0; // Find previous visited row of binary matrix // that has starting bit same as current row for (int i= 0 ; i < n ; i++) { // First look for same bit in trie if (temp->Child[ Mat[row_index][i] ] != NULL) temp = temp->Child[ Mat[row_index][i] ]; // Else looking for opposite bit else if (temp->Child[1 - Mat[row_index][i]] != NULL) { temp = temp->Child[1- Mat[row_index][i]]; count++; } } int leaf_index = temp->leaf; int count1 = 0 ; temp = root; // Find previous visited row of binary matrix // that has starting bit opposite to current row for (int i= 0 ; i < n ; i++) { // First looking for opposite bit if (temp->Child[ 1 - Mat[row_index][i] ] !=NULL) { temp = temp->Child[ 1- Mat[row_index][i] ]; count1++; } // Else look for same bit in trie else if (temp->Child[ Mat[row_index][i] ] != NULL) temp = temp->Child[ Mat[row_index][i] ]; } pair <int ,int> P = count1 > count ? make_pair(count1, temp->leaf): make_pair(count, leaf_index); // return pair that contain both bit difference // count and index of row with we get bit // difference return P;}// Returns maximum bit difference pair of rowvoid maxDiff( int mat[][MAX], int n, int m){ TrieNode * root = getNode(); // Insert first matrix row in trie insert(root, mat, m, 0); int max_bit_diff = INT_MIN; pair <int ,int> P, temp ; // Traverse all rest row of binary matrix for (int i = 1 ; i < n; i++) { // compute bit difference with previous visited // rows of matrix temp = maxBitDiffCount(root, mat, m ,i); // update maximum bit difference if (max_bit_diff < temp.first ) { max_bit_diff = temp.first; P = make_pair( temp.second, i+1); } // insert current row value into Trie insert(root, mat, m, i ); } // print maximum bit difference pair in row cout << "(" << P.first <<", "<< P.second << ")";}// Driver programint main(){ int mat[][MAX] = {{0 ,1 ,0 ,1, 0 }, {1, 0, 1 ,1 ,0 }, {0 ,0 ,1 ,0, 1 } }; maxDiff(mat, 3, 5) ; return 0;} |
Java
// Importing required libraryimport java.util.*;class Pair{ int first,second; Pair(int first,int second) { this.first = first; this.second = second; }}public class Main { // Maximum size of matrix static final int MAX = 100; static class TrieNode { int leaf; // store index of visited row TrieNode[] Child = new TrieNode[2]; // Constructor TrieNode() { this.leaf = 0; this.Child[0] = null; this.Child[1] = null; } } // Utility function to create a new Trie node static TrieNode getNode() { TrieNode newNode = new TrieNode(); return newNode; } // utility function insert new row in trie static void insert(TrieNode root, int[][] Mat, int n, int row_index) { TrieNode temp = root; for (int i = 0; i < n; i++) { // Add a new Node into trie if (temp.Child[(Mat[row_index][i])] == null) temp.Child[(Mat[row_index][i])] = getNode(); // move current node to point next node in trie temp = temp.Child[(Mat[row_index][i])]; } // store index of currently inserted row temp.leaf = row_index + 1; } // utility function calculate maximum bit difference of // current row with previous visited row of binary matrix static Pair maxBitDiffCount(TrieNode root, int[][] Mat, int n, int row_index) { TrieNode temp = root; int count = 0; // Find previous visited row of binary matrix // that has starting bit same as current row for (int i = 0; i < n; i++) { // First look for same bit in trie if (temp.Child[(Mat[row_index][i])] != null) temp = temp.Child[(Mat[row_index][i])]; // Else looking for opposite bit else if (temp.Child[1 - Mat[row_index][i]] != null) { temp = temp.Child[1 - Mat[row_index][i]]; count++; } } int leaf_index = temp.leaf; int count1 = 0; temp = root; // Find previous visited row of binary matrix // that has starting bit opposite to current row for (int i = 0; i < n; i++) { // First looking for opposite bit if (temp.Child[1 - Mat[row_index][i]] != null) { temp = temp.Child[1 - Mat[row_index][i]]; count1++; } // Else look for same bit in trie else if (temp.Child[(Mat[row_index][i])] != null) temp = temp.Child[(Mat[row_index][i])]; } Pair P = count1 > count ? new Pair(count1, temp.leaf) : new Pair(count, leaf_index); // return pair that contain both bit difference // count and index of row with we get bit // difference return P; } // Returns maximum bit difference pair of row static void maxDiff(int[][] mat, int n, int m) { TrieNode root = getNode(); // Insert first matrix row in trie insert(root, mat, m, 0); int max_bit_diff = Integer.MIN_VALUE; Pair P=null;Pair temp=null; // Traverse all rest row of binary matrix for (int i = 1; i < n; i++) { // compute bit difference with previous visited // rows of matrix temp = maxBitDiffCount(root, mat, m, i); // update maximum bit difference if (max_bit_diff < temp.first) { max_bit_diff = temp.first; P = new Pair(temp.second, i + 1); } // insert current row value into Trie insert(root, mat, m, i); } System.out.println("("+P.first+", "+P.second+")"); } public static void main(String[] args) { int mat[][] = {{0 ,1 ,0 ,1, 0 }, {1, 0, 1 ,1 ,0 }, {0 ,0 ,1 ,0, 1 } }; maxDiff(mat, 3, 5) ; }} |
Python3
import sys# Maximum size of matrixMAX = 100class TrieNode: def __init__(self): self.leaf = 0 # store index of visited row self.Child = [None] * 2# Utility function to create a new Trie nodedef getNode(): newNode = TrieNode() newNode.leaf = 0 newNode.Child = [None] * 2 return newNode# utility function insert new row in triedef insert(root, Mat, n, row_index): temp = root for i in range(n): # Add a new Node into trie if temp.Child[(Mat[row_index][i])] == None: temp.Child[(Mat[row_index][i])] = getNode() # move current node to point next node in trie temp = temp.Child[(Mat[row_index][i])] # store index of currently inserted row temp.leaf = row_index + 1# utility function calculate maximum bit difference of# current row with previous visited row of binary matrixdef maxBitDiffCount(root, Mat, n, row_index): temp = root count = 0 # Find previous visited row of binary matrix # that has starting bit same as current row for i in range(n): # First look for same bit in trie if temp.Child[(Mat[row_index][i])] != None: temp = temp.Child[(Mat[row_index][i])] # Else looking for opposite bit elif temp.Child[1 - Mat[row_index][i]] != None: temp = temp.Child[1 - Mat[row_index][i]] count += 1 leaf_index = temp.leaf count1 = 0 temp = root # Find previous visited row of binary matrix # that has starting bit opposite to current row for i in range(n): # First looking for opposite bit if temp.Child[1 - Mat[row_index][i]] != None: temp = temp.Child[1 - Mat[row_index][i]] count1 += 1 # Else look for same bit in trie elif temp.Child[(Mat[row_index][i])] != None: temp = temp.Child[(Mat[row_index][i])] P = (count1, temp.leaf) if count1 > count else (count, leaf_index) # return pair that contain both bit difference # count and index of row with we get bit # difference return P# Returns maximum bit difference pair of rowdef maxDiff(mat, n, m): root = getNode() # Insert first matrix row in trie insert(root, mat, m, 0) max_bit_diff = -sys.maxsize P, temp = None, None # Traverse all rest row of binary matrix for i in range(1, n): # compute bit difference with previous visited # rows of matrix temp = maxBitDiffCount(root, mat, m, i) # update maximum bit difference if max_bit_diff < temp[0]: max_bit_diff = temp[0] P = (temp[1], i+1) # insert current row value into Trie insert(root, mat, m, i) # print maximum bit difference pair in row print(f"({P[0]}, {P[1]})")# Driver programif __name__ == "__main__": mat = [[0, 1, 0 ,1, 0 ], [1, 0, 1 ,1 ,0 ], [0 ,0 ,1 ,0, 1 ] ] maxDiff(mat, 3, 5)# This code is contributed by Prince Kumar |
C#
// C# program to Find Pair of row in Binary matrix// that has maximum Bit differenceusing System;public class TrieNode{ public int Leaf;//store index of visited row public TrieNode[] Child; public TrieNode() { Leaf = 0; Child = new TrieNode[2]; Child[0] = Child[1] = null; }}public class MaxBitDifference{ // Maximum size of matrix private const int MAX = 100; // Utility function to create a new Trie node private static TrieNode GetNode() { return new TrieNode(); } // utility function insert new row in trie private static void Insert(TrieNode root, int[,] mat, int n, int rowIndex) { var temp = root; for (var i = 0; i < n; i++) { // Add a new Node into trie if (temp.Child[(mat[rowIndex, i])] == null) { temp.Child[(mat[rowIndex, i])] = GetNode(); } // move current node to point next node in trie temp = temp.Child[(mat[rowIndex, i])]; } // store index of currently inserted row temp.Leaf = rowIndex + 1; } // utility function calculate maximum bit difference of // current row with previous visited row of binary matrix private static Tuple<int, int> MaxBitDiffCount(TrieNode root, int[,] mat, int n, int rowIndex) { var temp = root; var count = 0; // Find previous visited row of binary matrix // that has starting bit same as current row for (var i = 0; i < n; i++) { // First look for same bit in trie if (temp.Child[(mat[rowIndex, i])] != null) { temp = temp.Child[(mat[rowIndex, i])]; } // Else looking for opposite bit else if (temp.Child[1 - mat[rowIndex, i]] != null) { temp = temp.Child[1 - mat[rowIndex, i]]; count++; } } var leafIndex = temp.Leaf; var count1 = 0; temp = root; // Find previous visited row of binary matrix // that has starting bit opposite to current row for (var i = 0; i < n; i++) { // First looking for opposite bit if (temp.Child[1 - mat[rowIndex, i]] != null) { temp = temp.Child[1 - mat[rowIndex, i]]; count1++; } // Else look for same bit in trie else if (temp.Child[(mat[rowIndex, i])] != null) { temp = temp.Child[(mat[rowIndex, i])]; } } var P = count1 > count ? new Tuple<int, int>(count1, temp.Leaf) : new Tuple<int, int>(count, leafIndex); // return pair that contain both bit difference // count and index of row with we get bit // difference return P; } // Returns maximum bit difference pair of row public static void MaxDiff(int[,] mat, int n, int m) { var root = GetNode(); // Insert first matrix row in trie Insert(root, mat, m, 0); var maxBitDiff = int.MinValue; Tuple<int, int> P = null, temp = null; // Traverse all rest row of binary matrix for (var i = 1; i < n; i++) { // compute bit difference with previous visited // rows of matrix temp = MaxBitDiffCount(root, mat, m, i); // update maximum bit difference if (maxBitDiff < temp.Item1) { maxBitDiff = temp.Item1; P = new Tuple<int, int>(temp.Item2, i + 1); } // insert current row value into Trie Insert(root, mat, m, i); } // print maximum bit difference pair in row Console.WriteLine("({0}, {1})", P.Item1, P.Item2); } // Driver program public static void Main() { var mat = new int[3, 5] {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 0}, {0, 0, 1, 0, 1}}; MaxDiff(mat, 3, 5); }} |
Javascript
// Maximum size of matrixconst MAX = 100;class TrieNode { constructor() { this.leaf = 0; // store index of visited row this.Child = [null, null]; }}// Utility function to create a new Trie nodefunction getNode() { const newNode = new TrieNode(); newNode.leaf = 0; newNode.Child = [null, null]; return newNode;}// utility function insert new row in triefunction insert(root, Mat, n, row_index) { let temp = root; for (let i = 0; i < n; i++) { // Add a new Node into trie if (temp.Child[(Mat[row_index][i])] == null) { temp.Child[(Mat[row_index][i])] = getNode(); } // move current node to point next node in trie temp = temp.Child[(Mat[row_index][i])]; } // store index of currently inserted row temp.leaf = row_index + 1;}// utility function calculate maximum bit difference of// current row with previous visited row of binary matrixfunction maxBitDiffCount(root, Mat, n, row_index) { let temp = root; let count = 0; // Find previous visited row of binary matrix // that has starting bit same as current row for (let i = 0; i < n; i++) { // First look for same bit in trie if (temp.Child[(Mat[row_index][i])] != null) { temp = temp.Child[(Mat[row_index][i])]; } // Else looking for opposite bit else if (temp.Child[1 - Mat[row_index][i]] != null) { temp = temp.Child[1 - Mat[row_index][i]]; count += 1; } } let leaf_index = temp.leaf; let count1 = 0; temp = root; // Find previous visited row of binary matrix // that has starting bit opposite to current row for (let i = 0; i < n; i++) { // First looking for opposite bit if (temp.Child[1 - Mat[row_index][i]] != null) { temp = temp.Child[1 - Mat[row_index][i]]; count1 += 1; } // Else look for same bit in trie else if (temp.Child[(Mat[row_index][i])] != null) { temp = temp.Child[(Mat[row_index][i])]; } } let P = count1 > count ? [count1, temp.leaf] : [count, leaf_index]; // return pair that contain both bit difference // count and index of row with we get bit // difference return P;}// Returns maximum bit difference pair of rowfunction maxDiff(mat, n, m) { const root = getNode(); // Insert first matrix row in trie insert(root, mat, m, 0); let max_bit_diff = -Infinity; let P = null; let temp = null; // Traverse all rest row of binary matrix for (let i = 1; i < n; i++) { // compute bit difference with previous visited // rows of matrix temp = maxBitDiffCount(root, mat, m, i); // update maximum bit difference if (max_bit_diff < temp[0]) { max_bit_diff = temp[0]; P = [temp[1], i + 1]; } // insert current row value into Trie insert(root, mat, m, i); } // print maximum bit difference pair in row console.log(`(${P[0]}, ${P[1]})`);}// Driver programconst mat = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 0], [0, 0, 1, 0, 1]];maxDiff(mat, 3, 5); |
Output
(1, 3)
Time Complexity:O(n)
Auxiliary Space: O(n)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
