Find the final string after flipping bits at the indices that are multiple of prime factors of array elements | Python program for the above approach ; Stores smallest prime factor ; Function to find the smallest prime factor for every number till MAXN ; Marking smallest prime factor for every number to be itself ; Separately marking spf for every even number as 2 ; Checking if i is prime ; Marking SPF for all numbers divisible by i ; Function to find all the distinct prime factors of the given number x ; Find the prime factors for X ; Find the spf [ ] of x ; Return the prime factors for x ; Function to find string after flipping the characters at indices of prime factors of array elements arr [ ] ; Precalculating Smallest Prime Factor ; Stores the frequency of each prime factor ; Iterate over all elements of the array arr [ ] ; Stores prime factors of arr [ i ] ; Increment the frequency of all prime factors of arr [ i ] ; Iterate over all elements of the array frequency [ ] ; If frequency [ i ] is odd ; Flip bits of all indices that are multiple of i ; Return Answer ; Driver Code
MAXN = 100001 NEW_LINE spf = [ 0 ] * MAXN NEW_LINE def sieve ( ) : NEW_LINE INDENT spf [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAXN ) : NEW_LINE INDENT spf [ i ] = i NEW_LINE DEDENT for i in range ( 4 , MAXN , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT i = 3 NEW_LINE while ( i * 8 < MAXN ) : NEW_LINE INDENT i += 1 NEW_LINE if ( spf [ i ] == i ) : NEW_LINE INDENT for j in range ( i * i , MAXN , i ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def getFactorization ( x ) : NEW_LINE INDENT ret = [ ] NEW_LINE while ( x != 1 ) : NEW_LINE INDENT ret . append ( spf [ x ] ) NEW_LINE value = spf [ x ] NEW_LINE while ( x % value == 0 ) : NEW_LINE INDENT x = x // value NEW_LINE DEDENT DEDENT return ret NEW_LINE DEDENT def flipString ( S , arr , M ) : NEW_LINE INDENT sieve ( ) ; NEW_LINE frequency = [ 0 ] * MAXN NEW_LINE for i in range ( 0 , M ) : NEW_LINE INDENT primeFactors = getFactorization ( arr [ i ] ) NEW_LINE for factors in primeFactors : NEW_LINE INDENT frequency [ factors ] += 1 NEW_LINE frequency [ factors ] %= 2 NEW_LINE DEDENT DEDENT N = len ( S ) NEW_LINE for i in range ( 0 , MAXN ) : NEW_LINE INDENT if ( frequency [ i ] & 1 ) : NEW_LINE INDENT for j in range ( i , N + 1 , i ) : NEW_LINE INDENT S [ j - 1 ] = ( '0' if S [ j - 1 ] == '1' else '1' ) NEW_LINE DEDENT DEDENT DEDENT return S NEW_LINE DEDENT S = "000000" NEW_LINE S = list ( S ) NEW_LINE arr = [ 2 , 4 , 6 ] NEW_LINE M = len ( arr ) NEW_LINE print ( " " . join ( flipString ( S , arr , M ) ) ) NEW_LINE