N / 3 repeated number in an array with O ( 1 ) space | PHP program to find if any element appears more than n / 3. ; take the integers as the maximum value of integer hoping the integer would not be present in the array ; if this element is previously seen , increment count1 . ; if this element is previously seen , increment count2 . ; if current element is different from both the previously seen variables , decrement both the counts . ; Again traverse the array and find the actual counts . ; Driver code
< ? php function appearsNBy3 ( $ arr , $ n ) { $ count1 = 0 ; $ count2 = 0 ; $ first = PHP_INT_MAX ; $ second = PHP_INT_MAX ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ first == $ arr [ $ i ] ) $ count1 ++ ; else if ( $ second == $ arr [ $ i ] ) $ count2 ++ ; else if ( $ count1 == 0 ) { $ count1 ++ ; $ first = $ arr [ $ i ] ; } else if ( $ count2 == 0 ) { $ count2 ++ ; $ second = $ arr [ $ i ] ; } else { $ count1 -- ; $ count2 -- ; } } $ count1 = 0 ; $ count2 = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ arr [ $ i ] == $ first ) $ count1 ++ ; else if ( $ arr [ $ i ] == $ second ) $ count2 ++ ; } if ( $ count1 > $ n / 3 ) return $ first ; if ( $ count2 > $ n / 3 ) return $ second ; return -1 ; } $ arr = array ( 1 , 2 , 3 , 1 , 1 ) ; $ n = count ( $ arr ) ; echo appearsNBy3 ( $ arr , $ n ) ; ? >