# Number from a given range that requires K^{th} smallest number of steps to get reduced to 1

Given three positive integers **L**, **R**, and **K**, the task is to find the number from the range **[L, R]** which requires **K ^{th}** smallest number of steps to be reduced to 1 by performing the following operations:

- If
**X**is even, then reduce**X**to**X/2**. - Otherwise, set
**X = (3*X + 1)**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:L = 7, R = 10, K = 4Output:9Explanation:

Count of steps for all the numbers from the range [7, 10] are as follows:

- The number of steps required for 7 is 16. {7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 > 1}
- Similarly, the number of steps required for 8 is 3.
- Similarly, the number of steps required for 9 is 19.
- Similarly, the number of steps required for 10 is 6.
Therefore, the number of steps required for all the values from the given range, sorted in ascending order, are {3, 6, 16, 19} for values {8, 10, 7, 9} respectively. Therefore, the K

^{th}smallest number of steps is required for the number 9.

Input:L = 7, R = 10, K = 2Output:10

**Approach:** The idea is to make separate functions to calculate the number of steps for each number from the range and print the **K ^{th}** smallest of the values obtained. Follow the steps below to solve the problem:

- Define a function
**power_value ()**to calculate the number of steps required for a number:- Base condition: If the
**number**is**1**, return**0**. - If the number is even, then call the function
**power_value()**with value**number/2**. - Otherwise, call the function
**power_value()**with value**number * 3 + 1**.

- Base condition: If the
- Now, for finding the
**K**, perform the following steps:^{th}smallest number of steps- Initialize a vector of pairs, say
**ans**. - Traverse the array in the range
**[L, R]**and calculate the power value of the current number**i**, and insert a pair of count of steps and**i**in the vector of pairs**ans**. - Sort the vector in ascending order of the count of steps of that number.

- Initialize a vector of pairs, say
- After completing the above steps, print the
**K**smallest count of steps from start, i.e.^{th}**ans[K – 1].second**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `#define ll long long int` `vector<ll> v(1000000, -1);` `// Function to count the number of` `// steps required to reduce val to` `// 1 by the given operations` `ll power_value(ll val)` `{` ` ` `// Base Case` ` ` `if` `(val == 1)` ` ` `return` `0;` ` ` `// If val is even, divide by 2` ` ` `if` `(val % 2 == 0) {` ` ` `v[val] = power_value(val / 2) + 1;` ` ` `return` `v[val];` ` ` `}` ` ` `// Otherwise, multiply it` ` ` `// by 3 and increment by 1` ` ` `else` `{` ` ` `ll temp = val * 3;` ` ` `temp++;` ` ` `v[val] = power_value(temp) + 1;` ` ` `return` `v[val];` ` ` `}` `}` `// Function to find Kth smallest` `// count of steps required for` `// numbers from the range [L, R]` `ll getKthNumber(` `int` `l, ` `int` `r, ` `int` `k)` `{` ` ` `// Stores numbers and their` ` ` `// respective count of steps` ` ` `vector<pair<ll, ll> > ans;` ` ` `// Count the number of steps for` ` ` `// all numbers from the range [L, R]` ` ` `for` `(ll i = l; i <= r; i++) {` ` ` `if` `(v[i] == -1)` ` ` `power_value(i);` ` ` `}` ` ` `ll j = 0;` ` ` `// Insert in the vector` ` ` `for` `(ll i = l; i <= r; i++) {` ` ` `ans.push_back(make_pair(v[i], i));` ` ` `j++;` ` ` `}` ` ` `// Sort the vector in ascending` ` ` `// order w.r.t. to power value` ` ` `sort(ans.begin(), ans.end());` ` ` `// Print the K-th smallest number` ` ` `cout << ans[k - 1].second;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `L = 7, R = 10, K = 4;` ` ` `getKthNumber(L, R, K);` ` ` `return` `0;` `}` |

## Python3

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

**Output:**

9

**Time Complexity:** O(N*log N)**Auxiliary Space:** O(N)