Largest smaller number possible using only one swap operation | Python3 program to find the largest smaller number by swapping one digit . ; Returns largest possible number with one swap such that the number is smaller than str . It is assumed that there are leading 0 s . ; Traverse from right until we find a digit which is greater than its next digit . For example , in 34125 , our index is 4. ; We can also use binary search here as digits after index are sorted in increasing order . Find the biggest digit in the right of arr [ index ] which is smaller than arr [ index ] ; If index is - 1 i . e . digits are in increasing order . ; Swap both values ; Driver Code
import sys NEW_LINE def prevNum ( string , n ) : NEW_LINE INDENT index = - 1 NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if int ( string [ i ] ) > int ( string [ i + 1 ] ) : NEW_LINE INDENT index = i NEW_LINE break NEW_LINE DEDENT DEDENT smallGreatDgt = - 1 NEW_LINE for i in range ( n - 1 , index , - 1 ) : NEW_LINE INDENT if ( smallGreatDgt == - 1 and int ( string [ i ] ) < int ( string [ index ] ) ) : NEW_LINE INDENT smallGreatDgt = i NEW_LINE DEDENT elif ( index > - 1 and int ( string [ i ] ) >= int ( string [ smallGreatDgt ] ) and int ( string [ i ] ) < int ( string [ index ] ) ) : NEW_LINE INDENT smallGreatDgt = i NEW_LINE DEDENT DEDENT if index == - 1 : NEW_LINE INDENT return " " . join ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT ( string [ index ] , string [ smallGreatDgt ] ) = ( string [ smallGreatDgt ] , string [ index ] ) NEW_LINE DEDENT return " " . join ( string ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n_str = "34125" NEW_LINE ans = prevNum ( list ( n_str ) , len ( n_str ) ) NEW_LINE print ( ans ) NEW_LINE DEDENT