Dados tres números enteros L , R y K donde [L, R] denota el rango de elementos, la tarea es encontrar el elemento en el rango [L, R] que requiere K th costo mínimo de conversión a 1 . Si dos o más elementos tienen el mismo costo, imprima el mínimo entre ellos.
El costo de conversión de un elemento X a 1 utilizando las operaciones dadas es el recuento de operaciones utilizadas:
- Si X es par, entonces convierte X a X/2
- Si X es impar, entonces convierta X a 3*X + 1
Ejemplos:
Entrada: L = 12, R = 15, K = 2
Salida: 13
Explicación:
El costo asociado con 12 es 9 (12 –> 6 –> 3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 -> 1)
El costo asociado con 13 es 9 (13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1)
El costo asociado con 14 es 17 ( 14 –> 7 –> 22 –> 11 –> 34 –> 17 –> 52 –> 26 –> 13 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 – > 1)
El costo asociado con 15 es 17 (15 –> 46–> 23 –> 70 –> 35 –> 106 –> 53 –> 160 –> 80 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)
El elemento ordenado según el costo es [12, 13, 14, 15].
Para K = 2, la salida es 13.Entrada: L = 1, R = 1, K = 1
Salida: 1
Enfoque ingenuo: el enfoque más simple es calcular el costo asociado con cada elemento entre L y R usando recursividad . A continuación se muestran los pasos:
- Defina una función func que calcule el costo recursivamente.
- Almacene todo el costo de los elementos en una array de pares.
- Ordena la array de pares según su costo.
- Luego devuelva el elemento en (K-1) el índice de la array.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
//Function to calculate the cost
int 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 element
void 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 Code
int 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 cost
static 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 element
static 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 code
public 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 cost def 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 element def 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 K l = 12 r = 15 k = 2 # Function Call findKthElement(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 cost
static 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 element
static 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 code
public 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 cost
function 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 element
function 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 K
var l = 12;
var r = 15;
var k = 2;
// Function call
findKthElement(l, r, k);
</script>
Producción:
13
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de programación dinámica . A continuación se muestran los pasos:
- Para evitar volver a calcular los subproblemas superpuestos , inicialice una array dp[] para almacenar el costo mínimo para llegar a 1 por cada subproblema encontrado.
- La relación de recurrencia para actualizar la tabla dp[] es:
dp[n] = 1 + func(n / 2) para elementos pares
dp[n] = 1 + func(3 * n + 1) para elementos impares
- Almacene todos los costos calculados en una array de pares
- Ordena la array de pares según su costo.
- Luego devuelve el elemento en (K – 1) th índice de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the cost
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 element
void 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 cost
static 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 element
static 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 cost
def 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 element
def 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 K
l = 12
r = 15
k = 2
# Function Call
findKthElement(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 cost
static 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 element
static 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 cost
function 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 element
function 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 K
let l = 12;
let r = 15;
let k = 2;
// Function call
findKthElement(l, r, k);
// This code is contributed by patel2127
</script>
Producción:
13
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA