Проверить, можно ли достичь точки (X, Y) из начала координат (0, 0) с помощью прыжка 1 и N перпендикулярно одновременно

Для данного положительного целого числа N и координат (X, Y) задача состоит в том, чтобы проверить, возможно ли достичь (X, Y) из (0, 0) с помощью прыжка 1 и N одновременно в перпендикулярном направлении. Если можно достичь (X, Y), то выведите Yes . В противном случае выведите Нет .

Примеры:

Input: N = 2, X = 5, Y = 4
Output: Yes
Explanation:
Following are the possible moves that leads to point (X, Y) from the current coordinate (0, 0):

1. Performing the jump of (2, 1) from the current coordinate modifies it to (2, 1).
2. Performing the jump of (2, 1) from the current coordinate modifies it to (4, 2).
3. Performing the jump of (1, 2) from the current coordinate modifies it to (5, 4).

Input: N = 3, X = 5, Y = 4
Output: No

Подход: Данную задачу можно решить, основываясь на наблюдении, что существует 4 возможных способа прыгнуть с любой координаты: (1, N), (1, -N), (-1, N) и (-1, -Н) . Далее, задачу можно разделить на 3 разных случая:

• Случай 1 - где N четно : в таких случаях достижима любая координата (X, Y). Давайте рассмотрим X и Y по одному. Для координаты X можно следовать последовательности (1, N), (1, -N), (1, N), (1, -N), … скачков. Результирующая координата будет либо (X, 0), которая является желаемой координатой, либо (X, N) . Поскольку N четно, последовательность прыжков (N, -1), (-N, -1), (N, -1), (N, -1), … также можно выполнить, чтобы достичь (X, 0) . Точно так же можно достичь (0, Y) и, комбинируя последовательность прыжков для достижения (X, 0) и (0, Y), можно достичь (X, Y) .
• Случай 2 — где N нечетно, а X и Y либо четны, либо нечетны : эти случаи можно обработать, выполнив последовательность операций, аналогичную случаю 1 .
• Случай 3 — когда N нечетно, а X и Y имеют разную четность : в таких случаях не существует возможной последовательности переходов для достижения (X, Y), потому что согласно случаю 2 (X + 1, Y) и (X, Y + 1) должен быть достижим, так как они оба будут иметь одинаковую четность, и нет возможной последовательности операций для покрытия расстояния (1, 0) или (0, 1) .

Следовательно, единственный случай, когда невозможно получить (X, Y) из (0, 0), — это когда N нечетно, а X и Y имеют разную четность, т. е. X четно, а Y нечетно, или наоборот.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)