Проверьте, можно ли преобразовать массив в другой, заменив пары на GCD.

Даны массивы A[] и B[], каждый из которых имеет длину N , а A[i] содержит все элементы от 1 до N. Задача состоит в том, чтобы проверить, можно ли преобразовать A[] в B[], заменив любую пару A[] с их НОД.

Примеры:

Input: N = 2, A[] = {1, 2}, B[] = {1, 1}
Output: YES 
Explanation:
First Operation – For A[], choose i = 0 and j = 1. GCD(A[0], A[1]) = GCD(1, 2) = 1. Replace both the elements with GCD = 1. So A[] = {1, 1}.

Input: N = 3, A[] = {1, 2, 3}, B[] = {1, 2, 2}
Output: NO
Explanation: It can be verify that it’s not possible to convert A[] to B[] by using given operation. 

Подход: реализуйте приведенную ниже идею, чтобы решить проблему.

The problem is observation based and can be solved by calculating GCD of A[i] and B[i] for each index. It should be noted that if B[i]>A[i] at any index, then it is impossible to change A[i] as B[i].

So, This idea gives us approach if GCD(A[i], B[i]) = B[i], Then it is possible to convert A[i] to B[i] at that index, else not possible.  

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте флаг логической переменной и инициализируйте его. истинный.
• Запустите цикл от i = 0 до N-1 :
  • Если НОД (А [я], В [я]) = В [я] затем продолжить цикл.
  • Еще отметьте флаг как ложный и разорвать цикл.
• Если флаг истинен, то выведите YES, иначе NO.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * logM), где M — максимальный элемент B[].
Вспомогательное пространство: O(1)

Эффективный подход:

In this approach, We don’t need to calculate GCD at each index, Which will save a little bit of time. For A[i] and B[i], There are 3 possible cases. Which are discussed below:

• If B[i] = A[i]: In such indices, We don’t need to perform the operation, Because A[i] is already equal to B[i].
• If B[i] < A[i]: In this case, A[i] can be converted to B[i] only and only if A[i] % B[i] = 0. Formally B[i] is a perfect divisor of A[i].
• If B[i] > A[i]: In this case, it is impossible to convert A[i] as B[i].

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте флаг логической переменной и инициализируйте его значением true.
• Запустите цикл от i = 0 до N-1:
  • Если A[i] и B[i] равны, то цикл продолжается.
  • В противном случае, если B[i] < A[i], то продолжаться, только если B[i] точно делит A[i].
  • В противном случае пометьте флаг как ложный и разорвите цикл .
• 3. Если флаг истинный вывод ДА иначе НЕТ.

Код для реализации подхода:

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам