Number from a given range that requires Kth smallest number of steps to get reduced to 1 | Python3 program for the above approach ; Function to count the number of steps required to reduce val to 1 by the given operations ; Base Case ; If val is even , divide by 2 ; Otherwise , multiply it by 3 and increment by 1 ; Function to find Kth smallest count of steps required for numbers from the range [ L , R ] ; Stores numbers and their respective count of steps ; Count the number of steps for anumbers from the range [ L , R ] ; Insert in the vector ; Sort the vector in ascending order w . r . t . to power value ; Print the K - th smallest number ; Driver Code
v = [ - 1 ] * ( 1000000 ) NEW_LINE def power_value ( val ) : NEW_LINE INDENT if ( val == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( val % 2 == 0 ) : NEW_LINE INDENT v [ val ] = power_value ( val // 2 ) + 1 NEW_LINE return v [ val ] NEW_LINE DEDENT else : NEW_LINE INDENT temp = val * 3 NEW_LINE temp += 1 NEW_LINE v [ val ] = power_value ( temp ) + 1 NEW_LINE return v [ val ] NEW_LINE DEDENT DEDENT def getKthNumber ( l , r , k ) : NEW_LINE INDENT ans = [ ] NEW_LINE for i in range ( l , r + 1 ) : NEW_LINE INDENT if ( v [ i ] == - 1 ) : NEW_LINE INDENT power_value ( i ) NEW_LINE DEDENT DEDENT j = 0 NEW_LINE for i in range ( l , r + 1 ) : NEW_LINE INDENT ans . append ( [ v [ i ] , i ] ) NEW_LINE j += 1 NEW_LINE DEDENT ans = sorted ( ans ) NEW_LINE print ( ans [ k - 1 ] [ 1 ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L , R , K = 7 , 10 , 4 NEW_LINE getKthNumber ( L , R , K ) NEW_LINE DEDENT