Dadas dos variables L y R , que indican un rango de números enteros de L a R inclusive, y un número K , la tarea es encontrar el K-ésimo número par más pequeño. Si K es mayor que una cantidad de números pares en el rango de L a R , devuelve -1. LLONG_MIN <= L <= R <= LLONG_MAX .
Ejemplos :
Entrada : L = 3, R = 9, K = 3
Salida : 8
Explicación : Los números pares en el rango son 4, 6, 8 y el tercer número par más pequeño es 8Entrada : L = -3, R = 3, K = 2
Salida : 0
Enfoque ingenuo: la idea básica es atravesar los números de L a R y luego imprimir el K-ésimo número par.
Tiempo Complejidad : O(RL)
Espacio Auxiliar : O(1)
Enfoque : El problema dado se puede resolver usando matemáticas básicas y usando techo y piso de la biblioteca cmath . La idea es comprobar si L es par o impar y calcular el K-ésimo número par más pequeño en consecuencia. Los siguientes pasos se pueden utilizar para resolver el problema:
- Si K<=0 entonces devuelve -1
- Inicialice el conteo para calcular el número de números pares dentro del rango
- Si L es impar
- cuenta = piso ((flotante) (R-L + 1)/2)
- Si K > cuenta devuelve -1
- De lo contrario regresa (L + 2*K – 1)
- Si L es par
- cuenta = techo ((flotante) (R-L+1)/2)
- Si K > cuenta devuelve -1
- Si no regresa (L + 2*K – 2)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <cmath>
#include <iostream>
#define ll long long
using namespace std;
// Function to return Kth smallest
// even number if it exists
ll findEven(ll L, ll R, ll K)
{
// Base Case
if (K <= 0)
return -1;
if (L % 2) {
// Calculate count of even numbers
// within the range
ll Count = floor((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 1);
}
else {
// Calculate count of even numbers
// within the range
ll Count = ceil((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 2);
}
}
// Driver Code
int main()
{
ll L = 3, R = 9, K = 3;
cout << findEven(L, R, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to return Kth smallest
// even number if it exists
static long findEven(long L, long R, long K)
{
// Base Case
if (K <= 0)
return -1;
if (L % 2 == 1) {
// Calculate count of even numbers
// within the range
long Count = (int)Math.floor((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 1);
}
else {
// Calculate count of even numbers
// within the range
long Count = (int)Math.ceil((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 2);
}
}
// Driver Code
public static void main(String args[])
{
long L = 3, R = 9, K = 3;
System.out.println(findEven(L, R, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program for the above approach # Function to return Kth smallest # even number if it exists def findEven(L, R, K): # Base Case if (K <= 0): return -1 if (L % 2): # Calculate count of even numbers # within the range Count = (R - L + 1) // 2 # if k > range then kth smallest # even number is not in this range # then return -1 return -1 if (K > Count) else (L + 2 * K - 1) else: # Calculate count of even numbers # within the range Count = (R - L + 1) // 2 # if k > range then kth smallest # even number is not in this range # then return -1 return -1 if (K > Count) else (L + 2 * K - 2) # Driver Code L = 3 R = 9 K = 3 print(findEven(L, R, K)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to return Kth smallest
// even number if it exists
static long findEven(long L, long R, long K)
{
// Base Case
if (K <= 0)
return -1;
if (L % 2 == 1) {
// Calculate count of even numbers
// within the range
long Count = (int)Math.Floor((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 1);
}
else {
// Calculate count of even numbers
// within the range
long Count = (int)Math.Ceiling((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 2);
}
}
// Driver Code
public static void Main()
{
long L = 3, R = 9, K = 3;
Console.Write(findEven(L, R, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to return Kth smallest
// even number if it exists
function findEven(L, R, K)
{
// Base Case
if (K <= 0)
return -1;
if (L % 2) {
// Calculate count of even numbers
// within the range
let Count = Math.floor((R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 1);
}
else {
// Calculate count of even numbers
// within the range
let Count = Math.ceil((float)(R - L + 1) / 2);
// if k > range then kth smallest
// even number is not in this range
// then return -1
return (K > Count) ? -1 : (L + 2 * K - 2);
}
}
// Driver Code
let L = 3, R = 9, K = 3;
document.write(findEven(L, R, K));
// This code is contributed by Samim Hossain Mondal.
</script>
8
Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA