K-е наибольшее нечетное число в заданном диапазоне
Даны две переменные L и R , обозначающие диапазон целых чисел от L до R включительно, и число K , задача состоит в том, чтобы найти K-е наибольшее нечетное число. Если K > количество нечетных чисел в диапазоне от L до R , верните 0.
Примеры :
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
Подход : Данную задачу можно решить с помощью математики. Идея состоит в том, чтобы проверить, является ли R нечетным или четным, и соответственно вычислить K-е наибольшее нечетное число. Следующие шаги могут быть использованы для решения проблемы:
- Если K<=0, то вернуть 0
- Инициализировать count , чтобы вычислить количество нечетных чисел в диапазоне
- Если R нечетное:
- count = ceil((с плавающей запятой)(R-L+1)/2)
- Если K > count вернуть 0
- В противном случае возврат (R - 2 * K + 2)
- Если R даже
- количество = этаж ((R-L+1)/2)
- Если K > count вернуть 0
- В противном случае возврат (R - 2 * K + 1)
Ниже приведена реализация вышеуказанного подхода:
Временная сложность : O(1)
Вспомогательное пространство : O(1)