N / 3 repeated number in an array with O ( 1 ) space | Javascript 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
function appearsNBy3 ( arr , n ) { let count1 = 0 , count2 = 0 ; let first = Number . MAX_VALUE ; let second = Number . MAX_VALUE ; for ( let i = 1 ; 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 ( let i = 0 ; i < n ; i ++ ) { if ( arr [ i ] == first ) count1 ++ ; else if ( arr [ i ] == second ) count2 ++ ; } if ( count1 > parseInt ( n / 3 , 10 ) ) return first ; if ( count2 > parseInt ( n / 3 , 10 ) ) return second ; return - 1 ; } let arr = [ 1 , 2 , 3 , 1 , 1 ] ; let n = arr . length ; document . write ( appearsNBy3 ( arr , n ) ) ;