Find the array element having equal count of Prime Numbers on its left and right | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findIndex ( int arr [ ] , int N ) { int maxValue = INT_MIN ; for ( int i = 0 ; i < N ; i ++ ) { maxValue = max ( maxValue , arr [ i ] ) ; } map < int , int > St ; for ( int i = 1 ; i <= maxValue ; i ++ ) { St [ i ] ++ ; } if ( St . find ( 1 ) != St . end ( ) ) { St . erase ( 1 ) ; } for ( int i = 2 ; i <= sqrt ( maxValue ) ; i ++ ) { int j = 2 ; while ( ( i * j ) <= maxValue ) { if ( St . find ( i * j ) != St . end ( ) ) { St . erase ( i * j ) ; } j ++ ; } } int LeftCount = 0 ; int Prefix [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { Prefix [ i ] = LeftCount ; if ( St . find ( arr [ i ] ) != St . end ( ) ) { LeftCount ++ ; } } int RightCount = 0 ; int Suffix [ N ] ; for ( int i = N - 1 ; i >= 0 ; i -- ) { Suffix [ i ] = RightCount ; if ( St . find ( arr [ i ] ) != St . end ( ) ) { RightCount ++ ; } } for ( int i = 0 ; i < N ; i ++ ) { if ( Prefix [ i ] == Suffix [ i ] ) { return i ; } } return -1 ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 7 , 5 , 10 , 1 , 8 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findIndex ( arr , N ) ; return 0 ; }