An in | Java implementation of above approach ; 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 code
import java . util . * ; class GFG { static char [ ] str ; static void reverse ( int low , int high ) { while ( low < high ) { char t = str [ low ] ; str [ low ] = str [ high ] ; str [ high ] = t ; ++ low ; -- high ; } } static void cycleLeader ( 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 % 2 == 1 ) j = len / 2 + j / 2 ; else j /= 2 ; char t = str [ j + shift ] ; str [ j + shift ] = item ; item = t ; } while ( j != i ) ; } } static void moveNumberToSecondHalf ( ) { int k , lenFirst ; int lenRemaining = str . length ; int shift = 0 ; while ( lenRemaining > 0 ) { k = 0 ; while ( Math . pow ( 3 , k ) + 1 <= lenRemaining ) k ++ ; lenFirst = ( int ) Math . pow ( 3 , k - 1 ) + 1 ; lenRemaining -= lenFirst ; cycleLeader ( shift , lenFirst ) ; reverse ( shift / 2 , shift - 1 ) ; reverse ( shift , shift + lenFirst / 2 - 1 ) ; reverse ( shift / 2 , shift + lenFirst / 2 - 1 ) ; shift += lenFirst ; } } public static void main ( String [ ] args ) { String st = " a1b2c3d4e5f6g7" ; str = st . toCharArray ( ) ; moveNumberToSecondHalf ( ) ; System . out . print ( str ) ; } }