Find the array element having equal count of Prime Numbers on its left and right | Python 3 program for the above approach ; Function to find the index of the array such that the count of prime numbers to its either ends are same ; Store the maximum value in the array ; Traverse the array arr [ ] ; / Stores all the numbers ; Iterate over the range [ 1 , Max ] ; Increment the value of st [ i ] ; Removes 1 from the map St ; Perform Sieve of Prime Numbers ; While i * j is less than the maxValue ; If i * j is in map St ; Erase the value ( i * j ) ; Increment the value of j ; Stores the count of prime from index 0 to i ; Stores the count of prime numbers ; Traverse the array arr [ ] ; If arr [ i ] is present in the map st ; Stores the count of prime from index i to N - 1 ; Stores the count of prime numbers ; Iterate over the range [ 0 , N - 1 ] in reverse order ; If arr [ i ] is in map st ; Iterate over the range [ 0 , N - 1 ] ; If prefix [ i ] is equal to the Suffix [ i ] ; Return - 1 if no such index is present ; Driver Code
from collections import defaultdict NEW_LINE import sys NEW_LINE import math NEW_LINE def findIndex ( arr , N ) : NEW_LINE INDENT maxValue = - sys . maxsize - 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT maxValue = max ( maxValue , arr [ i ] ) NEW_LINE DEDENT St = defaultdict ( int ) NEW_LINE for i in range ( 1 , maxValue + 1 ) : NEW_LINE INDENT St [ i ] += 1 NEW_LINE DEDENT if ( 1 in St ) : NEW_LINE INDENT St . pop ( 1 ) NEW_LINE DEDENT for i in range ( 2 , int ( math . sqrt ( maxValue ) ) + 1 ) : NEW_LINE INDENT j = 2 NEW_LINE while ( ( i * j ) <= maxValue ) : NEW_LINE INDENT if ( i * j ) in St : NEW_LINE INDENT St . pop ( i * j ) NEW_LINE DEDENT j += 1 NEW_LINE DEDENT DEDENT LeftCount = 0 NEW_LINE Prefix = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT Prefix [ i ] = LeftCount NEW_LINE if ( arr [ i ] in St ) : NEW_LINE INDENT LeftCount += 1 NEW_LINE DEDENT DEDENT RightCount = 0 NEW_LINE Suffix = [ 0 ] * N NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT Suffix [ i ] = RightCount NEW_LINE if arr [ i ] in St : NEW_LINE INDENT RightCount += 1 NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT if ( Prefix [ i ] == Suffix [ i ] ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 7 , 5 , 10 , 1 , 8 ] NEW_LINE N = len ( arr ) NEW_LINE print ( findIndex ( arr , N ) ) NEW_LINE DEDENT