Given two variables L and R, indicating a range of integers from L to R inclusive, and a number K, the task is to find Kth smallest even number. If K is greater than a number of even numbers in the range L to R then return -1. LLONG_MIN <= L <= R <= LLONG_MAX.
Examples:
Input: L = 3, R = 9, K = 3
Output: 8
Explanation: The even numbers in the range are 4, 6, 8 and the 3rd smallest even number is 8Input: L = -3, R = 3, K = 2
Output: 0
Naive Approach: The basic idea is to traverse the numbers from L to R, and then print the Kth even number.
Time Complexity: O(R-L)
Auxiliary Space: O(1)
Approach: The given problem can be solved using basic maths and using ceil and floor from cmath library. The idea is to check if L is odd or even and calculate Kth smallest even number accordingly. Below steps can be used to solve the problem:
- If K<=0 then return -1
- Initialize count to calculate the number of even numbers within the range
- If L is odd
- count = floor((float)(R-L+1)/2)
- If K > count return -1
- Else return (L + 2*K – 1)
- If L is even
- count = ceil((float)(R-L+1)/2)
- If K > count return -1
- Else return (L + 2*K – 2)
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <cmath>#include <iostream>#define ll long longusing namespace std;// Function to return Kth smallest// even number if it existsll 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 Codeint main(){ ll L = 3, R = 9, K = 3; cout << findEven(L, R, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{// Function to return Kth smallest// even number if it existsstatic 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 Codepublic 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 existsdef 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 CodeL = 3R = 9K = 3print(findEven(L, R, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG{// Function to return Kth smallest// even number if it existsstatic 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 Codepublic 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 existsfunction 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 Codelet L = 3, R = 9, K = 3;document.write(findEven(L, R, K));// This code is contributed by Samim Hossain Mondal.</script> |
Output
8
Time Complexity: O(1)
Auxiliary Space: O(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!
Share your thoughts in the comments
