Минимизировать разницу с 0 после добавления или вычитания любого элемента данного массива

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

Дан массив arr[] из N целых чисел, задача состоит в том, чтобы найти минимальное отличие от 0 после добавления или вычитания из него любого элемента массива.

Примеры:

Input: N = 4, arr[] = {1, 2, 1, 3}
Output: 1
Explanation: Add 1 and 2 with 0 and subtract 1 and 3.
So total sum = (1 + 2 – 1 – 3) = -1. Difference is 1.

Input: N = 3, arr[] = {3, 3, 3}
Output: 3
Explanation: No matter which order is chosen, the minimum possible difference is 3.

Input: N = 1, arr[] = {100}
Output: 100
Explanation: There is only one element so difference will be 100

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

  • Создайте рекурсивную функцию minDist , имеющую исходный массив аргументов arr , итерацию индекса r , начиная с 0 , длину массива N и целое число для вычисления текущего расстояния k .
  • Если r становится равным n , это означает, что все элементы пройдены, поэтому верните текущее расстояние k .
  • Иначе вернуть минимум minDist(arr, r+1, N, k+arr[r]) и minDist(arr, r+1, N, k-arr[r]) .

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


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

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