Print unique rows in a given boolean matrix | Given a binary matrix of M X N of integers , you need to return only unique rows of binary array ; A Trie node ; Only two children needed for 0 and 1 ; A utility function to allocate memory for a new Trie node ; Inserts a new matrix row to Trie . If row is already present , then returns 0 , otherwise insets the row and return 1 ; base case ; Recur if there are more entries in this row ; If all entries of this row are processed ; unique row found , return 1 ; duplicate row found , return 0 ; A utility function to print a row ; The main function that prints all unique rows in a given matrix . ; create an empty Trie ; Iterate through all rows ; insert row to TRIE ; unique row found , print it ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ROW  4 NEW_LINE #define COL  5 NEW_LINE class Node { public : bool isEndOfCol ; Node * child [ 2 ] ; } ; Node * newNode ( ) { Node * temp = new Node ( ) ; temp -> isEndOfCol = 0 ; temp -> child [ 0 ] = temp -> child [ 1 ] = NULL ; return temp ; } bool insert ( Node * * root , int ( * M ) [ COL ] , int row , int col ) { if ( * root == NULL ) * root = newNode ( ) ; if ( col < COL ) return insert ( & ( ( * root ) -> child [ M [ row ] [ col ] ] ) , M , row , col + 1 ) ; else { if ( ! ( ( * root ) -> isEndOfCol ) ) return ( * root ) -> isEndOfCol = 1 ; return 0 ; } } void printRow ( int ( * M ) [ COL ] , int row ) { int i ; for ( i = 0 ; i < COL ; ++ i ) cout << M [ row ] [ i ] << " ▁ " ; cout << endl ; } void findUniqueRows ( int ( * M ) [ COL ] ) { Node * root = NULL ; int i ; for ( i = 0 ; i < ROW ; ++ i ) if ( insert ( & root , M , i , 0 ) ) printRow ( M , i ) ; } int main ( ) { int M [ ROW ] [ COL ] = { { 0 , 1 , 0 , 0 , 1 } , { 1 , 0 , 1 , 1 , 0 } , { 0 , 1 , 0 , 0 , 1 } , { 1 , 0 , 1 , 0 , 0 } } ; findUniqueRows ( M ) ; return 0 ; }