Given a Boolean Matrix , find k such that all elements in k ' th ▁ row ▁ are ▁ 0 ▁ and ▁ k ' th column are 1. | C ++ program to find i such that all entries in i ' th ▁ row ▁ are ▁ 0 ▁ and ▁ all ▁ entries ▁ in ▁ i ' t column are 1 ; Start from top - most rightmost corner ( We could start from other corners also ) ; Initialize result ; Find the index ( This loop runs at most 2 n times , we either increment row number or decrement column number ) ; If current element is 0 , then this row may be a solution ; Check for all elements in this row ; If all values are 0 , then store this row as result ; We reach here if we found a 1 in current row , so this row cannot be a solution , increment row number ; If current element is 1 ; Check for all elements in this column ; If all elements are 1 ; We reach here if we found a 0 in current column , so this column cannot be a solution , increment column number ; If we could not find result in above loop , then result doesn 't exist ; Check if above computed res is valid ; Driver program to test above functions
#include <iostream> NEW_LINE using namespace std ; #define n  5 NEW_LINE int find ( bool arr [ n ] [ n ] ) { int i = 0 , j = n - 1 ; int res = -1 ; while ( i < n && j >= 0 ) { if ( arr [ i ] [ j ] == 0 ) { while ( j >= 0 && ( arr [ i ] [ j ] == 0 i == j ) ) j -- ; if ( j == -1 ) { res = i ; break ; } else i ++ ; } else { while ( i < n && ( arr [ i ] [ j ] == 1 i == j ) ) i ++ ; if ( i == n ) { res = j ; break ; } else j -- ; } } if ( res == -1 ) return res ; for ( int i = 0 ; i < n ; i ++ ) if ( res != i && arr [ i ] [ res ] != 1 ) return -1 ; for ( int j = 0 ; j < n ; j ++ ) if ( res != j && arr [ res ] [ j ] != 0 ) return -1 ; return res ; } int main ( ) { bool mat [ n ] [ n ] = { { 0 , 0 , 1 , 1 , 0 } , { 0 , 0 , 0 , 1 , 0 } , { 1 , 1 , 1 , 1 , 0 } , { 0 , 0 , 0 , 0 , 0 } , { 1 , 1 , 1 , 1 , 1 } } ; cout << find ( mat ) ; return 0 ; }