XOR of Prime Frequencies of Characters in a String | Python3 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
from collections import defaultdict NEW_LINE def SieveOfEratosthenes ( prime , p_size ) : NEW_LINE INDENT prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while p * p <= p_size : NEW_LINE INDENT if prime [ p ] : NEW_LINE INDENT for i in range ( p * 2 , p_size + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def xorOfPrime ( s ) : NEW_LINE INDENT prime = [ True ] * 100005 NEW_LINE SieveOfEratosthenes ( prime , 10005 ) NEW_LINE m = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , len ( s ) ) : NEW_LINE INDENT m [ s [ i ] ] += 1 NEW_LINE DEDENT result = flag = 0 NEW_LINE for it in m : NEW_LINE INDENT if prime [ m [ it ] ] : NEW_LINE INDENT result ^= m [ it ] NEW_LINE flag = 1 NEW_LINE DEDENT DEDENT if not flag : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return result NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " gggggeeekkkks " NEW_LINE print ( xorOfPrime ( s ) ) NEW_LINE DEDENT