Given a Boolean Matrix , find k such that all elements in k ' th ▁ row ▁ are ▁ 0 ▁ and ▁ k ' th column are 1. | PHP program to find i such that all entries in i ' th ▁ row ▁ are ▁ 0 ▁ and ▁ all ▁ entries ▁ in ▁ i ' th 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 Code
< ? php function find ( & $ arr ) { $ n = 5 ; $ i = 0 ; $ j = $ n - 1 ; $ 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 ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ res != $ i && $ arr [ $ i ] [ $ res ] != 1 ) return -1 ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) if ( $ res != $ j && $ arr [ $ res ] [ $ j ] != 0 ) return -1 ; return $ res ; } $ mat = array ( array ( 0 , 0 , 1 , 1 , 0 ) , array ( 0 , 0 , 0 , 1 , 0 ) , array ( 1 , 1 , 1 , 1 , 0 ) , array ( 0 , 0 , 0 , 0 , 0 ) , array ( 1 , 1 , 1 , 1 , 1 ) ) ; echo ( find ( $ mat ) ) ; ? >