Измените массив на другой заданный массив, заменив элементы массива суммой массива | Сет-2

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

Дан массив input[] изначально состоящий только из 1 s и массива target[] размера N , задача состоит в том, чтобы проверить, можно ли преобразовать массив input[] в target[] путем замены input[i] суммой элементов массива в каждый шаг.

Примеры:

Input: input[] = { 1, 1, 1 }, target[] = { 9, 3, 5 } 
Output: YES 
Explanation: 
Replacing input[1] with (input[0] + input[1] + input[2]) modifies input[] to { 1, 3, 1 } 
Replacing input[2] with (input[0] + input[1] + input[2]) modifies input[] to { 1, 3, 5 } 
Replacing input[0] with (input[0] + input[1] + input[2]) modifies input[] to { 9, 3, 5 } 
Since the array input[] equal to the target[] array, the required output is “YES”.

Input: input[] = { 1, 1, 1, 1 }, target[] = { 1, 1, 1, 2 } 
Output: NO

Наивный подход: наивный подход и жадный подход уже упоминались в Set-1 этой статьи.

Эффективный подход: Идея эффективного решения проблемы основана на следующей интуиции:

  • Instead of trying to check if target[] array can be reached, work backward and try to generate the array of 1s from the target[].
  • While working backward the maximum element of the array will be the sum of elements after the last turn. To keep track of the maximum element, use a max heap.
  • After every turn, remove the maximum element from the heap and determine the previous maximum element value. To do this find the sum of all elements of the array.

Следуйте инструкциям, чтобы решить проблему:

  • Создайте переменные sum и lastSum для хранения суммы всех элементов суммы массива на предыдущем шаге.
  • Чтобы определить предыдущий элемент, найдите отличие «sum» и «lastSum» от «lastSum», т.е. (lastSum – (sum – lastSum)).
  • Затем поместите это значение обратно в кучу и обновите сумму .
  • Продолжайте это до тех пор, пока сумма не станет равной единице или lastSum не станет равной единице.
  • В случае, если lastSum становится меньше суммы , или сумма становится равной нулю, или разница между lastSum и суммой становится равной нулю, возвращается false.

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

Временная сложность: O(N * log(N) + (K / N * log(N))), где K — максимальный элемент массива.
Вспомогательное пространство: O(N)

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