Given three integers L, R and K where [L, R] denotes the range of elements, the task is to find the element in the range [L, R] requiring Kth minimum cost of conversion to 1. If two or more elements have the same cost, then print the minimum among them.
Cost of conversion of an element X to 1 using the given operations is the count of operations used:
- If X is even, then convert X to X/2
- If X is odd, then convert X to 3*X + 1
Examples:
Input: L = 12, R = 15, K = 2
Output: 13
Explanation:
The cost associated with 12 is 9 (12 –> 6 –> 3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)
The cost associated with 13 is 9 (13 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)
The cost associated with 14 is 17 (14 –> 7 –> 22 –> 11 –> 34 –> 17 –> 52 –> 26 –> 13 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)
The cost associated with 15 is 17 (15 –> 46–> 23 –> 70 –> 35 –> 106 –> 53 –> 160 –> 80 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)
The element sorted according to cost is [12, 13, 14, 15].
For K = 2, the output is 13.Input: L = 1, R = 1, K = 1
Output: 1
Naive Approach: The simplest approach is to calculate the cost associated with each element between L and R using recursion. Below are the steps:
- Define a function func which calculates the cost recursively.
- Store all the cost of elements in an array of pairs.
- Sort the array of pairs according to their cost.
- Then return the element at (K-1)th index from the array.
Below is the implementation of the above approach:
C++14
// C++14 implementation of// the above approach#include <bits/stdc++.h>using namespace std;//Function to calculate the costint func(int n){ int count = 0; // Base case if (n == 2 or n == 1) return 1; // Even condition if (n % 2 == 0) count = 1 + func(n / 2); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1); // Return cost return count;}// Function to find Kth elementvoid findKthElement(int l, int r, int k){ vector<int> arr; for(int i = l; i <= r; i++) arr.push_back(i); // Array to store the costs vector<vector<int>> result; for(int i : arr) result.push_back({i, func(i)}); // Sort the array based on cost sort(result.begin(), result.end()); cout << (result[k - 1][0]);}// Driver Codeint main(){ // Given range and6 K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java implementation of // the above approach import java.util.*;class GFG{// Function to calculate the coststatic int func(int n){ int count = 0; // Base case if (n == 2 || n == 1) return 1; // Even condition if (n % 2 == 0) count = 1 + func(n / 2); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1); // Return cost return count;}// Function to find Kth elementstatic void findKthElement(int l, int r, int k){ ArrayList<Integer> arr = new ArrayList<>(); for(int i = l; i <= r; i++) arr.add(i); // Array to store the costs ArrayList<List<Integer>> result = new ArrayList<>(); for(int i : arr) result.add(Arrays.asList(i, func(i))); // Sort the array based on cost Collections.sort(result, (s1, s2) -> s1.get(1) - s2.get(1)); System.out.println(result.get(k - 1).get(0));}// Driver codepublic static void main (String[] args) { // Given range and6 K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k); }}// This code is contributed by offbeat |
Python3
# Python3 implementation of # the above approach# Function to calculate the costdef func(n): count = 0 # Base case if n == 2 or n == 1: return 1 # Even condition if n % 2 == 0: count = 1 + func(n//2) # Odd condition if n % 2 != 0: count = 1 + func(n * 3 + 1) # Return cost return count# Function to find Kth elementdef findKthElement(l, r, k): arr = list(range(l, r + 1)) # Array to store the costs result = [] for i in arr: result.append([i, func(i)]) # Sort the array based on cost result.sort() print(result[k-1][0])# Driver Code# Given range and Kl = 12r = 15k = 2# Function CallfindKthElement(l, r, k) |
C#
// C# implementation of // the above approach using System;using System.Linq;using System.Collections.Generic;class GFG{// Function to calculate the coststatic int func(int n){ int count = 0; // Base case if (n == 2 || n == 1) return 1; // Even condition if (n % 2 == 0) count = 1 + func(n / 2); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1); // Return cost return count;}// Function to find Kth elementstatic void findKthElement(int l, int r, int k){ List<int> arr = new List<int>(); for(int i = l; i <= r; i++) arr.Add(i); // Array to store the costs Dictionary<int, int> result = new Dictionary<int, int>(); foreach(int i in arr) { result.Add(i, func(i)); } // Sort the array based on cost var myList = result.ToList(); myList.Sort((pair1, pair2) => pair1.Value.CompareTo( pair2.Value)); Console.WriteLine(myList[1].Key);}// Driver codepublic static void Main(String[] args) { // Given range and6 K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k); }}// This code is contributed by aashish1995 |
Javascript
<script>// JavaScript implementation of// the above approach//Function to calculate the costfunction func(n){ var count = 0; // Base case if (n == 2 || n == 1) return 1; // Even condition if (n % 2 == 0) count = 1 + func(n / 2); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1); // Return cost return count;}// Function to find Kth elementfunction findKthElement( l, r, k){ var arr = []; for(var i = l; i <= r; i++) arr.push(i); // Array to store the costs var result = []; arr.forEach(i => { result.push([i, func(i)]); }); // Sort the array based on cost result.sort(); document.write( result[k - 1][0]);}// Driver Code// Given range and6 Kvar l = 12;var r = 15;var k = 2;// Function callfindKthElement(l, r, k);</script> |
Output:
13
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient approach: The above approach can be optimized by using Dynamic Programming. Below are the steps:
- To avoid recalculating the overlapping subproblems, initialize a dp[] array to store the minimum cost to reach 1 from for every encountered subproblem.
- The recurrence relation to update the dp[] table is :
dp[n] = 1 + func(n / 2) for even elements
dp[n] = 1 + func(3 * n + 1) for odd elements
- Store all the calculated costs in an array of pairs
- Sort the array of pairs according to their cost.
- Then return the element at (K – 1)th index from the array.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h>using namespace std;// Function to calculate the costint func(int n, int dp[]){ int count = 0; // Base case if (n == 2 || n == 1) return 1; if (dp[n] != -1) return dp[n]; // Even condition if (n % 2 == 0) count = 1 + func(n / 2, dp); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1, dp); // Store the result dp[n] = count; return dp[n];}// Function to find Kth elementvoid findKthElement(int l, int r, int k){ // Array to store the results vector<pair<int, int> > result; // Define DP array int dp[r + 1] = {0}; dp[1] = 1; dp[2] = 1; for(int i = l; i <= r; i++) result.push_back({i, func(i, dp)}); // Sort the array based on cost sort(result.begin(), result.end()); cout << (result[k - 1].first);}// Driver code int main(){ // Given range and K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k);}// This code is contributed by grand_master |
Java
// Java implementation of // the above approach import java.util.*;class GFG{ static class Pair implements Comparable<Pair>{ int start,end; Pair(int s, int e) { start = s; end = e; } public int compareTo(Pair p) { return this.start - p.start; }}// Function to calculate // the coststatic int func(int n, int dp[]){ int count = 0; // Base case if (n == 2 || n == 1) return 1; if (dp[n] != -1) return dp[n]; // Even condition if (n % 2 == 0) count = 1 + func(n / 2, dp); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1, dp); // Store the result dp[n] = count; return dp[n];}// Function to find Kth elementstatic void findKthElement(int l, int r, int k){ // Array to store the // results Vector<Pair> result = new Vector<>(); // Define DP array int []dp = new int[r + 1]; dp[1] = 1; dp[2] = 1; for(int i = l; i <= r; i++) result.add(new Pair(i, func(i, dp))); // Sort the array based // on cost Collections.sort(result); System.out.print( result.get(k - 1).start);}// Driver code public static void main(String[] args){ // Given range and K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 implementation of the above approach# Function to calculate the costdef func(n, dp): count = 0 # Base case if n == 2 or n == 1: return 1 if n in dp: return dp[n] # Even condition if n % 2 == 0: count = 1 + func(n//2, dp) # Odd condition if n % 2 != 0: count = 1 + func(n * 3 + 1, dp) # Store the result dp[n]= count return dp[n] # Function to find Kth elementdef findKthElement(l, r, k): arr = list(range(l, r + 1)) # Array to store the results result = [] # Define DP array dp ={1:1, 2:1} for i in arr: result.append([i, func(i, dp)]) # Sort the array based on cost result.sort() print(result[k-1][0])# Given range and Kl = 12r = 15k = 2# Function CallfindKthElement(l, r, k) |
C#
// C# implementation of // the above approach using System;using System.Collections;class GFG{ class Pair{ public int start,end; public Pair(int s, int e) { start = s; end = e; }}class sortHelper : IComparer{ int IComparer.Compare(object a, object b) { Pair first=(Pair)a; Pair second=(Pair)b; return first.start - second.start; }} // Function to calculate // the coststatic int func(int n, int []dp){ int count = 0; // Base case if (n == 2 || n == 1) return 1; if (dp[n] != -1) return dp[n]; // Even condition if (n % 2 == 0) count = 1 + func(n / 2, dp); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1, dp); // Store the result dp[n] = count; return dp[n];} // Function to find Kth elementstatic void findKthElement(int l, int r, int k){ // Array to store the // results ArrayList result = new ArrayList(); // Define DP array int []dp = new int[r + 1]; dp[1] = 1; dp[2] = 1; for(int i = l; i <= r; i++) result.Add(new Pair(i, func(i, dp))); // Sort the array based // on cost result.Sort(new sortHelper()); Console.Write(((Pair)result[k - 1]).start);} // Driver code public static void Main(string[] args){ // Given range and K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript implementation of// the above approach// Function to calculate// the costfunction func(n,dp){ let count = 0; // Base case if (n == 2 || n == 1) return 1; if (dp[n] != -1) return dp[n]; // Even condition if (n % 2 == 0) count = 1 + func(Math.floor(n / 2), dp); // Odd condition if (n % 2 != 0) count = 1 + func(n * 3 + 1, dp); // Store the result dp[n] = count; return dp[n];}// Function to find Kth elementfunction findKthElement(l,r,k){ // Array to store the // results let result = []; // Define DP array let dp = new Array(r + 1); dp[1] = 1; dp[2] = 1; for(let i = l; i <= r; i++) result.push([i, func(i, dp)]); // Sort the array based // on cost result.sort(function(a,b){return a[0]-b[0];}); document.write( result[k-1][0]);}// Driver code// Given range and Klet l = 12;let r = 15;let k = 2;// Function callfindKthElement(l, r, k);// This code is contributed by patel2127</script> |
Output:
13
Time Complexity: O(N*M)
Auxiliary Space: O(N)
Efficient approach: Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a vector DP to store the solution of the subproblems and initialize it with 0.
- Initialize the dp with base cases and compute for even and odd conditions.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Return the final solution.
Implementation :
C++
// C++ program for above apprach#include <bits/stdc++.h>using namespace std;// Function to calculate the costvoid func(int n, vector<int>& dp){ dp[1] = 1; dp[2] = 1; for(int i = 3; i <= n; i++) { // Even condition if (i % 2 == 0) dp[i] = 1 + dp[i / 2]; // Odd condition else dp[i] = 1 + dp[i * 3 + 1]; }}// Function to find Kth elementvoid findKthElement(int l, int r, int k){ // Define DP array vector<int> dp(r + 1, 0); func(r, dp); // Array to store the results vector<pair<int, int> > result; for(int i = l; i <= r; i++) result.push_back({i, dp[i]}); // Sort the array based on cost sort(result.begin(), result.end()); cout << result[k - 1].first;}// Driver codeint main(){ // Given range and K int l = 12; int r = 15; int k = 2; // Function call findKthElement(l, r, k);}// this code is contributed by bhardwajji |
Java
import java.util.*;class GFG { // Function to calculate the cost static int[] func(int n) { int[] dp = new int[n + 1]; // Base case dp[1] = 1; // Iterate for all elements for (int i = 2; i <= n; i++) { dp[i] = 1 + dp[i - 1]; // If even then divide by 2 if (i % 2 == 0) { dp[i] = Math.min(dp[i], 1 + dp[i / 2]); } // If odd then divide by 2 and add 1 else { dp[i] = Math.min(dp[i], 2 + dp[(i + 1) / 2]); } } return dp; } public static void main(String[] args) { int l = 12; int r = 15; int k = 2; // Function call int[] dp = func(r); // Create list of tuples with indices and costs List<int[]> lst = new ArrayList<>(); for (int i = l; i <= r; i++) { lst.add(new int[]{i, dp[i]}); } // Sort the list based on cost lst.sort(Comparator.comparingInt(a -> a[1])); // Print k-th element index System.out.println(lst.get(k - 1)[0]); }} |
Python3
# Python program for above apprachdef func(n): dp = [0] * (n + 1) # Base case dp[1] = 1 # Iterate for all elements for i in range(2, n + 1): dp[i] = 1 + dp[i - 1] # If even then divide by 2 if i % 2 == 0: dp[i] = min(dp[i], 1 + dp[i // 2]) # If odd then divide by 2 and add 1 else: dp[i] = min(dp[i], 2 + dp[(i + 1) // 2]) return dp# Driver codeif __name__ == '__main__': l, r, k = 12, 15, 2 # Function call dp = func(r) # Create list of tuples with indices and costs lst = [(i, dp[i]) for i in range(l, r+1)] # Sort the list based on cost lst.sort(key=lambda x: x[1]) # Print k-th element index print(lst[k-1][0]) |
Javascript
function func(n) { let dp = Array(n+1).fill(0); // Base case dp[1] = 1; // Iterate for all elements for (let i = 2; i <= n; i++) { dp[i] = 1 + dp[i-1]; // If even then divide by 2 if (i % 2 === 0) { dp[i] = Math.min(dp[i], 1 + dp[i/2]); } // If odd then divide by 2 and add 1 else { dp[i] = Math.min(dp[i], 2 + dp[(i+1)/2]); } } return dp;}// Driver codelet l = 12, r = 15, k = 2;// Function calllet dp = func(r);// Create list of tuples with indices and costslet lst = Array.from({length: r-l+1}, (_, i) => [i+l, dp[i+l]]);// Sort the list based on costlst.sort((a, b) => a[1] - b[1]);// Print k-th element indexconsole.log(lst[k-1][0]); |
C#
using System;using System.Collections.Generic;class Program { static int[] Func(int n) { int[] dp = new int[n + 1]; // Base case dp[1] = 1; // Iterate for all elements for (int i = 2; i <= n; i++) { dp[i] = 1 + dp[i - 1]; // If even then divide by 2 if (i % 2 == 0) { dp[i] = Math.Min(dp[i], 1 + dp[i / 2]); } // If odd then divide by 2 and add 1 else { dp[i] = Math.Min(dp[i], 2 + dp[(i + 1) / 2]); } } return dp; } static void FindKthElement(int l, int r, int k) { int[] dp = Func(r); // Create list of tuples with indices and costs List<(int, int)> lst = new List<(int, int)>(); for (int i = l; i <= r; i++) { lst.Add((i, dp[i])); } // Sort the list based on cost lst.Sort((x, y) => x.Item2.CompareTo(y.Item2)); // Print k-th element index Console.WriteLine(lst[k - 1].Item1); } static void Main(string[] args) { int l = 12; int r = 15; int k = 2; // Function call FindKthElement(l, r, k); }} |
Output
13
Time Complexity: O(r log r), The time complexity of the findKthElement function is O(r log r)
Auxiliary Space: O(r), since it creates a DP array of size r+1
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
