Number from a given range that requires Kth smallest number of steps to get reduced to 1 | C ++ 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 all numbers 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE vector < ll > v ( 1000000 , -1 ) ; ll power_value ( ll val ) { if ( val == 1 ) return 0 ; if ( val % 2 == 0 ) { v [ val ] = power_value ( val / 2 ) + 1 ; return v [ val ] ; } else { ll temp = val * 3 ; temp ++ ; v [ val ] = power_value ( temp ) + 1 ; return v [ val ] ; } } ll getKthNumber ( int l , int r , int k ) { vector < pair < ll , ll > > ans ; for ( ll i = l ; i <= r ; i ++ ) { if ( v [ i ] == -1 ) power_value ( i ) ; } ll j = 0 ; for ( ll i = l ; i <= r ; i ++ ) { ans . push_back ( make_pair ( v [ i ] , i ) ) ; j ++ ; } sort ( ans . begin ( ) , ans . end ( ) ) ; cout << ans [ k - 1 ] . second ; } int main ( ) { int L = 7 , R = 10 , K = 4 ; getKthNumber ( L , R , K ) ; return 0 ; }