An in | C ++ implementation of above approach ; A utility function to swap characters ; A utility function to reverse string str [ low . . high ] ; Cycle leader algorithm to move all even positioned elements at the end . ; odd index ; even index ; keep the back - up of element at new position ; The main function to transform a string . This function mainly uses cycleLeader ( ) to transform ; Step 1 : Find the largest prefix subarray of the form 3 ^ k + 1 ; Step 2 : Apply cycle leader algorithm for the largest subarrau ; Step 4.1 : Reverse the second half of first subarray ; Step 4.2 : Reverse the first half of second sub - string . ; Step 4.3 Reverse the second half of first sub - string and first half of second sub - string together ; Increase the length of first subarray ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void swap ( char * a , char * b ) { char t = * a ; * a = * b ; * b = t ; } void reverse ( char * str , int low , int high ) { while ( low < high ) { swap ( & str [ low ] , & str [ high ] ) ; ++ low ; -- high ; } } void cycleLeader ( char * str , int shift , int len ) { int j ; char item ; for ( int i = 1 ; i < len ; i *= 3 ) { j = i ; item = str [ j + shift ] ; do { if ( j & 1 ) j = len / 2 + j / 2 ; else j /= 2 ; swap ( & str [ j + shift ] , & item ) ; } while ( j != i ) ; } } void moveNumberToSecondHalf ( char * str ) { int k , lenFirst ; int lenRemaining = strlen ( str ) ; int shift = 0 ; while ( lenRemaining ) { k = 0 ; while ( pow ( 3 , k ) + 1 <= lenRemaining ) k ++ ; lenFirst = pow ( 3 , k - 1 ) + 1 ; lenRemaining -= lenFirst ; cycleLeader ( str , shift , lenFirst ) ; reverse ( str , shift / 2 , shift - 1 ) ; reverse ( str , shift , shift + lenFirst / 2 - 1 ) ; reverse ( str , shift / 2 , shift + lenFirst / 2 - 1 ) ; shift += lenFirst ; } } int main ( ) { char str [ ] = " a1b2c3d4e5f6g7" ; moveNumberToSecondHalf ( str ) ; cout << str ; return 0 ; }