Rearrange the given string such that all prime multiple indexes have same character | CPP program to rearrange the given string such that all prime multiple indexes have same character ; To store answer ; Function to rearrange the given string such that all prime multiple indexes have the same character . ; Initially assume that we can kept any symbol at any positions . If at any index contains one then it is not counted in our required positions ; To store number of positions required to store elements of same kind ; Start sieve ; For all multiples of i ; map to store frequency of each character ; Store all characters in the vector and sort the vector to find the character with highest frequency ; If most occured character is less than required positions ; In all required positions keep character which occured most times ; Fill all other indexes with remaining characters ; If character frequency becomes zero then go to next character ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE char ans [ N ] ; int sieve [ N ] ; void Rearrange ( string s , int n ) { fill ( sieve + 1 , sieve + n + 1 , 1 ) ; int sz = 0 ; for ( int i = 2 ; i <= n / 2 ; i ++ ) { if ( sieve [ i ] ) { for ( int j = 1 ; i * j <= n ; j ++ ) { if ( sieve [ i * j ] ) sz ++ ; sieve [ i * j ] = 0 ; } } } map < char , int > m ; for ( auto it : s ) m [ it ] ++ ; vector < pair < int , char > > v ; for ( auto it : m ) v . push_back ( { it . second , it . first } ) ; sort ( v . begin ( ) , v . end ( ) ) ; if ( v . back ( ) . first < sz ) { cout << -1 ; return ; } for ( int i = 2 ; i <= n ; i ++ ) { if ( ! sieve [ i ] ) { ans [ i ] = v . back ( ) . second ; } } int idx = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( sieve [ i ] ) { ans [ i ] = v [ idx ] . second ; v [ idx ] . first -- ; if ( v [ idx ] . first == 0 ) idx ++ ; } cout << ans [ i ] ; } } int main ( ) { string str = " aabaaaa " ; int n = str . size ( ) ; Rearrange ( str , n ) ; return 0 ; }