Найдите элементы в заданном массиве, которые являются фактором суммы оставшихся элементов

Учитывая массив A[] размера N , задача состоит в том, чтобы найти элементы в массиве, которые являются факторами суммы оставшегося элемента. Так что просто выберите элемент из массива и возьмите сумму оставшихся элементов и проверьте, делится ли сумма на выбранный элемент или нет. Если он делится, верните элемент.

Примеры:

Input: A[] = {2, 4, 6, 8, 10, 12, 14}
Output: [2, 4, 8, 14]
Explanation: 
1. Take sum for remaining element except selected one.
2. For element 2, sum of remaining element is 4+6+8+10+12+14=54 
3. Similarly for complete array: [54, 52, 50, 48, 46, 44, 42]
3. 54/2, 52/4, 48/8, 42/14 are perfectly divisible so resultant elements are [2, 4, 8, 14]

Input: A[]= {3, 6, 8, 10, 7, 15}
Output: [7]

Наивный подход: возьмите сумму всех элементов массива. Теперь вычтите каждый элемент один за другим из суммы и добавьте его в новый массив p[]. Разделите каждую сумму на соответствующий элемент индекса из заданного массива и добавьте его к новому массиву q[]. Умножьте соответствующий элемент из массива A[] и массива q[] и сравните его с аналогичными индексированными элементами из массива p[] . Если они равны, добавьте их в новый массив z[ ] . Если такой элемент не найден, верните -1.

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

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

Эффективный подход: в этом подходе нет необходимости использовать несколько циклов и несколько массивов. поэтому сложность пространства и сложность времени будут уменьшены. При этом все операции вычитания, деления, умножения выполняются в одном цикле. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную s как сумму массива A[].
• Инициализируйте массив z[] для сохранения результата.
• Перебрать диапазон [0, len(A)) с использованием переменных i и выполнить следующие задачи:
  • Инициализируйте переменную a как sl[i], b как a/A[i].
  • Если b*A[i] равно a, добавьте A[i] в z[].
• После выполнения вышеуказанных шагов выведите -1 , если результирующий массив пуст, иначе в качестве ответа выведите элементы массива z[] .

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

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