An in | 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
def Reverse ( string : list , low : int , high : int ) : NEW_LINE INDENT while low < high : NEW_LINE INDENT string [ low ] , string [ high ] = string [ high ] , string [ low ] NEW_LINE low += 1 NEW_LINE high -= 1 NEW_LINE DEDENT DEDENT def cycleLeader ( string : list , shift : int , len : int ) : NEW_LINE INDENT i = 1 NEW_LINE while i < len : NEW_LINE INDENT j = i NEW_LINE item = string [ j + shift ] NEW_LINE while True : NEW_LINE INDENT if j & 1 : NEW_LINE INDENT j = len // 2 + j // 2 NEW_LINE DEDENT else : NEW_LINE INDENT j //= 2 NEW_LINE DEDENT string [ j + shift ] , item = item , string [ j + shift ] NEW_LINE if j == i : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT i *= 3 NEW_LINE DEDENT DEDENT def moveNumberToSecondHalf ( string : list ) : NEW_LINE INDENT k , lenFirst = 0 , 0 NEW_LINE lenRemaining = len ( string ) NEW_LINE shift = 0 NEW_LINE while lenRemaining : NEW_LINE INDENT k = 0 NEW_LINE while pow ( 3 , k ) + 1 <= lenRemaining : NEW_LINE INDENT k += 1 NEW_LINE DEDENT lenFirst = pow ( 3 , k - 1 ) + 1 NEW_LINE lenRemaining -= lenFirst NEW_LINE cycleLeader ( string , shift , lenFirst ) NEW_LINE Reverse ( string , shift // 2 , shift - 1 ) NEW_LINE Reverse ( string , shift , shift + lenFirst // 2 - 1 ) NEW_LINE Reverse ( string , shift // 2 , shift + lenFirst // 2 - 1 ) NEW_LINE shift += lenFirst NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " a1b2c3d4e5f6g7" NEW_LINE string = list ( string ) NEW_LINE moveNumberToSecondHalf ( string ) NEW_LINE print ( ' ' . join ( string ) ) NEW_LINE DEDENT