Find the final string after flipping bits at the indices that are multiple of prime factors of array elements | JavaScript 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
const MAXN = 100001 ; let spf = new Array ( MAXN ) . fill ( 0 ) ; const sieve = ( ) => { spf [ 1 ] = 1 ; for ( let i = 2 ; i < MAXN ; i ++ ) spf [ i ] = i ; for ( let i = 4 ; i < MAXN ; i += 2 ) spf [ i ] = 2 ; for ( let i = 3 ; i * i < MAXN ; i ++ ) { if ( spf [ i ] == i ) { for ( let j = i * i ; j < MAXN ; j += i ) { if ( spf [ j ] == j ) spf [ j ] = i ; } } } } const getFactorization = ( x ) => { let ret = [ ] ; while ( x != 1 ) { ret . push ( spf [ x ] ) ; let value = spf [ x ] ; while ( x % value == 0 ) x = parseInt ( x / value ) ; } return ret ; } const flipString = ( S , arr , M ) => { sieve ( ) ; let frequency = new Array ( MAXN ) . fill ( 0 ) ; for ( let i = 0 ; i < M ; i ++ ) { let primeFactors = getFactorization ( arr [ i ] ) ; for ( let factors in primeFactors ) { frequency [ primeFactors [ factors ] ] ++ ; frequency [ factors ] %= 2 ; } } let N = S . length ; for ( let i = 0 ; i < MAXN ; i ++ ) { if ( frequency [ i ] & 1 ) { for ( let j = i ; j <= N ; j += i ) { S [ j - 1 ] = ( S [ j - 1 ] == ' ' ? ' ' : ' ' ) ; } } } return S ; } let S = " " ; S = S . split ( " " ) ; let arr = [ 2 , 4 , 6 ] ; let M = arr . length ; document . write ( flipString ( S , arr , M ) . join ( ' ' ) ) ;