Find the array element having equal sum of Prime Numbers on its left and right | Java program for the above approach ; Function to find an index in the array having sum of prime numbers to its left and right equal ; Stores the maximum value present in the array ; Stores all positive elements which are <= max_value ; If 1 is present ; Remove 1 ; Sieve of Eratosthenes to store all prime numbers which are <= max_value in the Map ; Erase non - prime numbers ; Stores the sum of prime numbers from left ; Stores the sum of prime numbers to the left of each index ; Stores the sum of prime numbers to the left of the current index ; Add current value to the prime sum if the current value is prime ; Stores the sum of prime numbers from right ; Stores the sum of prime numbers to the right of each index ; Stores the sum of prime numbers to the right of the current index ; Add current value to the prime sum if the current value is prime ; Traverse through the two arrays to find the index ; Compare the values present at the current index ; Return the index where both the values are same ; No index is found . ; Driver code ; Given array arr [ ] ; Size of Array ; Function Call
import java . lang . * ; import java . util . * ; class GFG { static int find_index ( int arr [ ] , int N ) { int max_value = Integer . MIN_VALUE ; for ( int i = 0 ; i < N ; i ++ ) { max_value = Math . max ( max_value , arr [ i ] ) ; } Map < Integer , Integer > store = new HashMap < > ( ) ; for ( int i = 1 ; i <= max_value ; i ++ ) { store . put ( i , store . getOrDefault ( i , 0 ) + 1 ) ; } if ( store . containsKey ( 1 ) ) { store . remove ( 1 ) ; } for ( int i = 2 ; i <= Math . sqrt ( max_value ) ; i ++ ) { int multiple = 2 ; while ( ( i * multiple ) <= max_value ) { if ( store . containsKey ( i * multiple ) ) { store . remove ( i * multiple ) ; } multiple ++ ; } } int prime_sum_from_left = 0 ; int [ ] first_array = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { first_array [ i ] = prime_sum_from_left ; if ( store . containsKey ( arr [ i ] ) ) { prime_sum_from_left += arr [ i ] ; } } int prime_sum_from_right = 0 ; int [ ] second_array = new int [ N ] ; for ( int i = N - 1 ; i >= 0 ; i -- ) { second_array [ i ] = prime_sum_from_right ; if ( store . containsKey ( arr [ i ] ) ) { prime_sum_from_right += arr [ i ] ; } } for ( int i = 0 ; i < N ; i ++ ) { if ( first_array [ i ] == second_array [ i ] ) { return i ; } } return - 1 ; } public static void main ( String [ ] args ) { int arr [ ] = { 11 , 4 , 7 , 6 , 13 , 1 , 5 } ; int N = arr . length ; System . out . println ( find_index ( arr , N ) ) ; } }