XOR of Prime Frequencies of Characters in a String | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void SieveOfEratosthenes ( bool 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 ; } } } int xorOfPrime ( string s ) { bool prime [ 100005 ] ; memset ( prime , true , sizeof ( prime ) ) ; SieveOfEratosthenes ( prime , 10005 ) ; int i , j ; map < char , int > m ; for ( i = 0 ; i < s . length ( ) ; i ++ ) m [ s [ i ] ] ++ ; int result = 0 ; int flag = 0 ; for ( auto it = m . begin ( ) ; it != m . end ( ) ; it ++ ) { if ( prime [ it -> second ] ) { result ^= it -> second ; flag = 1 ; } } if ( ! flag ) return -1 ; return result ; } int main ( ) { string s = " gggggeeekkkks " ; cout << xorOfPrime ( s ) ; return 0 ; }