Frequency of an integer in the given array using Divide and Conquer | Function to return the frequency of x in the subarray arr [ low ... high ] ; If the subarray is invalid or the element is not found ; If there 's only a single element  which is equal to x ; Divide the array into two parts and then find the count of occurrences of x in both the parts ; Driver code
def count ( arr , low , high , x ) : NEW_LINE INDENT if ( ( low > high ) or ( low == high and arr [ low ] != x ) ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( low == high and arr [ low ] == x ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT return count ( arr , low , ( low + high ) // 2 , x ) + count ( arr , 1 + ( low + high ) // 2 , high , x ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 30 , 1 , 42 , 5 , 56 , 3 , 56 , 9 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE x = 56 ; NEW_LINE print ( count ( arr , 0 , n - 1 , x ) ) ; NEW_LINE DEDENT