Проверьте, можно ли уменьшить 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ