Number from a given range that requires Kth 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 Kth 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:
Input: L = 7, R = 10, K = 4
Output: 9
Explanation:
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 Kth smallest number of steps is required for the number 9.
Input: L = 7, R = 10, K = 2
Output: 10
Approach: The idea is to make separate functions to calculate the number of steps for each number from the range and print the Kth 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.
- Now, for finding the Kth smallest number of steps, perform the following 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.
- After completing the above steps, print the Kth smallest count of steps from start, i.e. 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; } |
Java
import java.util.*; class GFG { static long v[] = new long [ 1000001 ]; // Function to count the number of // steps required to reduce val to // 1 by the given operations static long powerValue( long val) { // Base Case if (val == 1 ) { return 0 ; } // If val is even, divide by 2 if (val % 2 == 0 ) { v[( int )val] = powerValue(( int )(val / 2 )) + 1 ; return v[( int )val]; } // Otherwise, multiply it // by 3 and increment by 1 else { long temp = val * 3 ; temp += 1 ; v[( int )val] = powerValue(temp) + 1 ; return v[( int )val]; } } // Function to find Kth smallest // count of steps required for // numbers from the range [L, R] static void getKthNumber( long l, long r, int k) { // Stores numbers and their // respective count of steps ArrayList< long []> ans = new ArrayList< long []>(); Arrays.fill(v, - 1 ); // Count the number of steps for // all numbers from the range [L, R] for ( long i = l; i <= r; i++) { if (v[( int )i] == - 1 ) { v[( int )i] = powerValue(i); } } long j = 0 ; // Insert in the vector for ( long i = l; i <= r; i++) { long [] arr = { v[( int )j], i }; ans.add(arr); j += 1 ; } // Sort the vector in ascending // order w.r.t. to power value Collections.sort( ans, (a, b) -> Long.compare(a[ 0 ], b[ 0 ])); // Print the K-th smallest number System.out.println(ans.get(k - 1 )[ 1 ]); } // Driver Code public static void main(String[] args) { long L = 7 , R = 10 ; int K = 4 ; getKthNumber(L, R, K); } } // This code is contributed by phasing17. |
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. |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; class Program { static long [] v = Enumerable.Repeat(-1L, 1000000).ToArray(); // Function to count the number of // steps required to reduce val to // 1 by the given operations static long powerValue( long val) { // Base Case if (val == 1) { return 0; } // If val is even, divide by 2 if (val % 2 == 0) { v[val] = powerValue(( int )(val / 2)) + 1; return v[val]; } // Otherwise, multiply it // by 3 and increment by 1 else { long temp = val * 3; temp += 1; v[val] = powerValue(temp) + 1; return v[val]; } } // Function to find Kth smallest // count of steps required for // numbers from the range [L, R] static void getKthNumber( long l, long r, long k) { // Stores numbers and their // respective count of steps List< long []> ans = new List< long []>(); // Count the number of steps for // all numbers from the range [L, R] for ( long i = l; i <= r; i++) { if (v[i] == -1) { v[i] = powerValue(i); } } long j = 0; // Insert in the vector for ( long i = l; i <= r; i++) { ans.Add( new long [] { v[i], i }); j += 1; } // Sort the vector in ascending // order w.r.t. to power value ans.Sort((a, b) => ( int )(a[0] - b[0])); // Print the K-th smallest number Console.WriteLine(ans[( int )k - 1][1]); } // Driver Code static void Main( string [] args) { long L = 7, R = 10, K = 4; getKthNumber(L, R, K); } } // This code is contributed by phasing17 |
Javascript
// JavaScript program for the above approach let v = new Array(1000000).fill(-1); // Function to count the number of // steps required to reduce val to // 1 by the given operations function powerValue(val) { // Base Case if (val === 1) { return 0; } // If val is even, divide by 2 if (val % 2 === 0) { v[val] = powerValue(val / 2) + 1; return v[val]; } // Otherwise, multiply it // by 3 and increment by 1 else { let temp = val * 3; temp += 1; v[val] = powerValue(temp) + 1; return v[val]; } } // Function to find Kth smallest // count of steps required for // numbers from the range [L, R] function getKthNumber(l, r, k) { // Stores numbers and their // respective count of steps let ans = []; // Count the number of steps for // anumbers from the range [L, R] for (let i = l; i <= r; i++) { if (v[i] === -1) { powerValue(i); } } let j = 0; // Insert in the vector for (let i = l; i <= r; i++) { ans.push([v[i], i]); j += 1; } // Sort the vector in ascending // order w.r.t. to power value ans.sort((a, b) => a[0] - b[0]); // Print the K-th smallest number console.log(ans[k - 1][1]); } // Driver Code ( function () { let L = 7; let R = 10; let K = 4; getKthNumber(L, R, K); })(); // This code is contributed by phasing17 |
9
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Contact Us