Find the final string after flipping bits at the indices that are multiple of prime factors of array elements | C ++ 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
#include " bits / stdc + + . h " NEW_LINE using namespace std ; #define MAXN  100001 NEW_LINE int spf [ MAXN ] ; void sieve ( ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < MAXN ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < MAXN ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < MAXN ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < MAXN ; j += i ) { if ( spf [ j ] == j ) spf [ j ] = i ; } } } } vector < int > getFactorization ( int x ) { vector < int > ret ; while ( x != 1 ) { ret . push_back ( spf [ x ] ) ; int value = spf [ x ] ; while ( x % value == 0 ) x = x / value ; } return ret ; } string flipString ( string S , int arr [ ] , int M ) { sieve ( ) ; int frequency [ MAXN ] = { 0 } ; for ( int i = 0 ; i < M ; i ++ ) { vector < int > primeFactors = getFactorization ( arr [ i ] ) ; for ( auto & factors : primeFactors ) { frequency [ factors ] ++ ; frequency [ factors ] %= 2 ; } } int N = S . length ( ) ; for ( int i = 0 ; i < MAXN ; i ++ ) { if ( frequency [ i ] & 1 ) { for ( int j = i ; j <= N ; j += i ) { S [ j - 1 ] = ( S [ j - 1 ] == '1' ? '0' : '1' ) ; } } } return S ; } int main ( ) { string S = "000000" ; int arr [ ] = { 2 , 4 , 6 } ; int M = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << flipString ( S , arr , M ) ; return 0 ; }