N / 3 repeated number in an array with O ( 1 ) space | Java 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
class GFG { static int appearsNBy3 ( int arr [ ] , int n ) { int count1 = 0 , count2 = 0 ; int first = Integer . MIN_VALUE ; ; int second = Integer . MAX_VALUE ; for ( int 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 ( int 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 ; } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 2 , 3 , 1 , 1 } ; int n = arr . length ; System . out . println ( appearsNBy3 ( arr , n ) ) ; } }