Проверьте, можно ли уменьшить A и B до 0, уменьшив x и y с абсолютной разницей не более K
Опубликовано: 21 Сентября, 2022
Даны три целых числа A , B и K . Задача состоит в том, чтобы проверить, могут ли A и B быть уменьшены до нуля путем уменьшения x и y из A и B соответственно так, что abs(x – y) ≤ K .
Пример:
Input: A = 2, B = 7, K = 3
Output: YES
Explanation: Decrement values in the following way:
- Decrement 1 from A and 4 from B such that abs(1 – 4) ≤ 3, therefore, current value of A = 1 and B = 3.
- Decrement 1 from A and 3 from B such that abs(1 – 3) ≤ 3, current value of A = 0 and B = 0.
So, it is possible to reduce both the numbers to 0.
Input: A = 9, B = 8, K = 0
Output: NO
Подход: Задачу можно решить простым наблюдением . Идея состоит в том, чтобы найти минимум и максимум из A и B. Если минимальное число, умноженное на ( 1 + K ), меньше максимального, то невозможно преобразовать A и B в ноль, иначе они могут быть преобразованы в ноль.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(1)
Вспомогательное пространство: O(1)