Find the array element having equal count of Prime Numbers on its left and right | Java 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
import java . util . HashMap ; public class GFG { static int findIndex ( int arr [ ] , int N ) { int maxValue = Integer . MIN_VALUE ; for ( int i = 0 ; i < N ; i ++ ) { maxValue = Math . max ( maxValue , arr [ i ] ) ; } HashMap < Integer , Integer > St = new HashMap < > ( ) ; for ( int i = 1 ; i <= maxValue ; i ++ ) { St . put ( i , St . getOrDefault ( i , 0 ) + 1 ) ; } if ( St . containsKey ( 1 ) ) { St . remove ( 1 ) ; } for ( int i = 2 ; i <= Math . sqrt ( maxValue ) ; i ++ ) { int j = 2 ; while ( ( i * j ) <= maxValue ) { if ( St . containsKey ( i * j ) ) { St . remove ( i * j ) ; } j ++ ; } } int LeftCount = 0 ; int Prefix [ ] = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { Prefix [ i ] = LeftCount ; if ( St . containsKey ( arr [ i ] ) ) { LeftCount ++ ; } } int RightCount = 0 ; int Suffix [ ] = new int [ N ] ; for ( int i = N - 1 ; i >= 0 ; i -- ) { Suffix [ i ] = RightCount ; if ( St . containsKey ( arr [ i ] ) ) { RightCount ++ ; } } for ( int i = 0 ; i < N ; i ++ ) { if ( Prefix [ i ] == Suffix [ i ] ) { return i ; } } return - 1 ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 4 , 7 , 5 , 10 , 1 , 8 } ; int N = arr . length ; System . out . println ( findIndex ( arr , N ) ) ; } }