Минимизируйте операцию увеличения-уменьшения на соседних элементах, чтобы преобразовать массив A в B

Даны два массива A[] и B[] , состоящие из N положительных целых чисел, задача состоит в том, чтобы найти минимальное количество приращений и декрементов соседних элементов массива A[] , необходимое для преобразования его в массив B[] . Если это невозможно, то выведите «-1» .

Примеры:

Input: A[] = {1, 2}, B[] = {2, 1}
Output: 1
Explanation:
Perform the following operations on the array A[]:

1. Consider the adjacent pairs (arr[0], arr[1]) and after incrementing and decrementing the pairs modifies the array A[] to {2, 1}.

After the above operation, the array A[] = {2, 1} is equal to B and the minimum number of operation required is 1. 

Input: A[] = {1, 0, 0}, B[] = {2, 3, 1}
Output: -1

Подход: Данная проблема может быть решена с использованием жадного подхода. Ниже приведены шаги:

• Можно заметить, что если сумма массивов A[] и B[] не равна, то допустимой последовательности операций не существует. В этом случае ответ будет -1 .
• В противном случае обойдите данный массив A[] и выполните следующие шаги в соответствии со следующими случаями:
  1. Случай, когда A[i] > B[i]:
     • В этом случае следите за дополнительными значениями (т. е . A[i] — B[i] ). Итерируйте с помощью указателя j из [i — 1, 0] и продолжайте добавлять дополнительные значения к индексам до тех пор, пока A[j] < B[j] до тех пор, пока дополнительные значения не будут исчерпаны (A[i] – B[i] не станет 0 ) или не будет достигнут конец массива. Точно так же перейдите вправо [i + 1, N – 1] и продолжайте добавлять дополнительные значения.
     • Следите за количеством ходов в переменной и для перевода 1 из индекса i в индекс j минимальное количество необходимых операций равно |i – j| .
  2. Случай, когда A[i] <= B[i] . В этом случае выполните итерацию к следующему значению i , потому что эти индексы будут учитываться при итерации в рассмотренном выше случае.

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

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