XOR of Prime Frequencies of Characters in a String | Java program to find XOR of Prime Frequencies of Characters in a String ; Function to create Sieve to check primes ; false here indicates that it is not prime ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function to find XOR of prime frequencies ; map is used to store character frequencies ; Traverse the map ; Calculate XOR of all prime frequencies ; Driver code
import java . util . * ; class GFG { static void SieveOfEratosthenes ( boolean prime [ ] , int p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( int i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } static int xorOfPrime ( char [ ] s ) { boolean [ ] prime = new boolean [ 100005 ] ; for ( int i = 0 ; i < 100005 ; i ++ ) prime [ i ] = true ; SieveOfEratosthenes ( prime , 10005 ) ; int i , j ; Map < Character , Integer > m = new HashMap < > ( ) ; for ( i = 0 ; i < s . length ; i ++ ) { if ( m . containsKey ( s [ i ] ) ) { m . put ( s [ i ] , m . get ( s [ i ] ) + 1 ) ; } else { m . put ( s [ i ] , 1 ) ; } } int result = 0 ; int flag = 0 ; for ( Map . Entry < Character , Integer > entry : m . entrySet ( ) ) { if ( prime [ entry . getValue ( ) ] ) { result ^= entry . getValue ( ) ; flag = 1 ; } } if ( flag != 1 ) return - 1 ; return result ; } public static void main ( String [ ] args ) { char [ ] s = " gggggeeekkkks " . toCharArray ( ) ; System . out . println ( xorOfPrime ( s ) ) ; } }