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 largest odd number. If K > number of odd numbers in the range L to R then return 0.
Examples:
Input: L = -10, R = 10, K = 8
Output: -5
Explanation: The odd Numbers in the range are -9, -7, -5, -3, -1, 1, 3, 5, 7, 9 and the 8th Largest odd number is -5Input: L = -3, R = 3, K = 1
Output: 3
Approach: The given problem can be solved using mathematics. The idea is to check if R is odd or even and calculate Kth largest odd number accordingly. Below steps can be used to solve the problem:
- If K<=0 then return 0
- Initialize count to calculate the number of odd numbers within the range
- If R is odd:
- count = ceil((float)(R-L+1)/2)
- If K > count return 0
- Else return (R – 2*K + 2)
- If R is even
- count = floor((R-L+1)/2)
- If K > count return 0
- Else return (R – 2*K + 1)
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <cmath>#include <iostream>using namespace std;// Function to return Kth largest// odd number if it existsint kthOdd(pair<int, int> range, int K){ // Base Case if (K <= 0) return 0; int L = range.first; int R = range.second; if (R & 1) { // Calculate count of odd // numbers within the range int Count = ceil((float)(R - L + 1) / 2); // if k > range then kth largest // odd number is not in the range if (K > Count) return 0; else return (R - 2 * K + 2); } else { // Calculate count of odd // numbers within the range int Count = (R - L + 1) / 2; // If k > range then kth largest // odd number is not in this range if (K > Count) return 0; else return (R - 2 * K + 1); }}// Driver Codeint main(){ // Initialize the range pair<int, int> p = { -10, 10 }; // Initialize k int k = 8; // print the kth odd number cout << kthOdd(p, k); return 0;} |
Java
// Java implementation for the above approachclass GFG { // Function to return Kth largest // odd number if it exists public static int kthOdd(int[] range, int K) { // Base Case if (K <= 0) return 0; int L = range[0]; int R = range[1]; if ((R & 1) > 0) { // Calculate count of odd // numbers within the range int Count = (int) Math.ceil((R - L + 1) / 2); // if k > range then kth largest // odd number is not in the range if (K > Count) return 0; else return (R - 2 * K + 2); } else { // Calculate count of odd // numbers within the range int Count = (R - L + 1) / 2; // If k > range then kth largest // odd number is not in this range if (K > Count) return 0; else return (R - 2 * K + 1); } } // Driver Code public static void main(String args[]) { // Initialize the range int[] p = { -10, 10 }; // Initialize k int k = 8; // print the kth odd number System.out.println(kthOdd(p, k)); }}// This code is contributed by gfgking. |
Python3
# python implementation for the above approachimport math# Function to return Kth largest# odd number if it existsdef kthOdd(range, K): # Base Case if (K <= 0): return 0 L = range[0] R = range[1] if (R & 1): # Calculate count of odd # numbers within the range Count = math.ceil((R - L + 1) / 2) # if k > range then kth largest # odd number is not in the range if (K > Count): return 0 else: return (R - 2 * K + 2) else: # Calculate count of odd # numbers within the range Count = (R - L + 1) // 2 # If k > range then kth largest # odd number is not in this range if (K > Count): return 0 else: return (R - 2 * K + 1)# Driver Codeif __name__ == "__main__": # Initialize the range p = [-10, 10] # Initialize k k = 8 # print the kth odd number print(kthOdd(p, k))# This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;public class GFG{ // Function to return Kth largest // odd number if it exists public static int kthOdd(int[] range, int K) { // Base Case if (K <= 0) return 0; int L = range[0]; int R = range[1]; if ((R & 1) > 0) { // Calculate count of odd // numbers within the range int Count = ((R - L + 1) / 2); // if k > range then kth largest // odd number is not in the range if (K > Count) return 0; else return (R - 2 * K + 2); } else { // Calculate count of odd // numbers within the range int Count = (R - L + 1) / 2; // If k > range then kth largest // odd number is not in this range if (K > Count) return 0; else return (R - 2 * K + 1); } } // Driver Code public static void Main(string[] args) { // Initialize the range int[] p = { -10, 10 }; // Initialize k int k = 8; // print the kth odd number Console.WriteLine(kthOdd(p, k)); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to return Kth largest // odd number if it exists function kthOdd(range, K) { // Base Case if (K <= 0) return 0; let L = range.first; let R = range.second; if (R & 1) { // Calculate count of odd // numbers within the range let Count = Math.ceil((R - L + 1) / 2); // if k > range then kth largest // odd number is not in the range if (K > Count) return 0; else return (R - 2 * K + 2); } else { // Calculate count of odd // numbers within the range let Count = (R - L + 1) / 2; // If k > range then kth largest // odd number is not in this range if (K > Count) return 0; else return (R - 2 * K + 1); } } // Driver Code // Initialize the range let p = { first: -10, second: 10 }; // Initialize k let k = 8; // print the kth odd number document.write(kthOdd(p, k)); // This code is contributed by Potta Lokesh </script> |
Output
-5
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach: using NumPy:
Python3
import numpy as npdef kth_largest_odd_number(start, end, k): # create an array of odd numbers within the range odd_numbers = np.array([x for x in range(start, end+1) if x % 2 != 0]) # sort the array in descending order sorted_odd_numbers = np.sort(odd_numbers)[::-1] # return the kth largest odd number return sorted_odd_numbers[k-1]if __name__ == '__main__': start = -10 end = 10 k = 8 result = kth_largest_odd_number(start, end, k) print(result) |
output
-5
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!
