N / 3 repeated number in an array with O ( 1 ) space | Python 3 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
import sys NEW_LINE def appearsNBy3 ( arr , n ) : NEW_LINE INDENT count1 = 0 NEW_LINE count2 = 0 NEW_LINE first = sys . maxsize NEW_LINE second = sys . maxsize NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if ( first == arr [ i ] ) : NEW_LINE INDENT count1 += 1 NEW_LINE DEDENT elif ( second == arr [ i ] ) : NEW_LINE INDENT count2 += 1 NEW_LINE DEDENT elif ( count1 == 0 ) : NEW_LINE INDENT count1 += 1 NEW_LINE first = arr [ i ] NEW_LINE DEDENT elif ( count2 == 0 ) : NEW_LINE INDENT count2 += 1 NEW_LINE second = arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT count1 -= 1 NEW_LINE count2 -= 1 NEW_LINE DEDENT DEDENT count1 = 0 NEW_LINE count2 = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if ( arr [ i ] == first ) : NEW_LINE INDENT count1 += 1 NEW_LINE DEDENT elif ( arr [ i ] == second ) : NEW_LINE INDENT count2 += 1 NEW_LINE DEDENT DEDENT if ( count1 > n / 3 ) : NEW_LINE INDENT return first NEW_LINE DEDENT if ( count2 > n / 3 ) : NEW_LINE INDENT return second NEW_LINE DEDENT return - 1 NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 1 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( appearsNBy3 ( arr , n ) ) NEW_LINE