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