Проверьте, можно ли сделать две координаты равными, увеличив/уменьшив их на K1 и K2 соответственно.
Имея две целочисленные координаты (X1, Y1) и (X2, Y2) и два положительных целых числа K1 и K2 , задача состоит в том, чтобы проверить, можно ли сделать обе координаты равными, выполнив следующие шаги любое количество раз:
- Добавьте или вычтите K1 из одной или обеих координат (X1, Y1) .
- Добавьте или вычтите K2 из одной или обеих координат (X2, Y2) .
Если можно сделать (X1, Y1) и (X2, Y2) равными, то выведите Yes . В противном случае выведите Нет .
Примеры:
Input: X1 = 10, Y1 = 10, X2 = 18, Y2 = 13, K1 = 3, K2 = 4
Output: Yes
Explanation:
Following are the moves that can be taken to make both the coordinates equal:
- Move point (X1, Y1) as (10, 10) -> (10, 13).
- Move point (X2, Y2) as (18, 13) -> (14, 13) -> (10, 13)
From the above operations, both the coordinates can be made equal, then print Yes.
Input: X1 = 10, Y1 = 10, X2 = 18, Y2 = 13, K1 = 10, K2 = 10
Output: No
Подход: эта проблема может быть решена с помощью жадного подхода, основанного на наблюдении, что движения могут быть предприняты в направлении x для точки (X1, Y1) равно n1 , а перемещения в направлении x для точки (X2, Y2) равны n2. , то выражение можно записать в виде:
n1*K1 + n2*K2 = abs(X1 – X2),
…where n1 and n2 are non negative integers.
Аналогично то же самое можно записать для направления Y как:
n3*K1 + n4*K2 = abs(Y1 – Y2),
…where n3 and n4 are non negative integers.
Теперь можно видеть, что проблема сводится к тому, чтобы выяснить, имеет ли приведенное выше уравнение решения или нет. Если оба уравнения имеют неотрицательные решения, выведите «Да» . В противном случае выведите «Нет» .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(log(max(K1, K2)))
Вспомогательное пространство: O(1)