Проверьте, можно ли сделать две координаты равными, увеличив/уменьшив их на K1 и K2 соответственно.

Опубликовано: 21 Сентября, 2022

Имея две целочисленные координаты (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:

  1. Move point (X1, Y1) as (10, 10) -> (10, 13).
  2. 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)

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