Найти последний оставшийся элемент массива после многократной сортировки и вычитания соседних

Дан массив arr[] длины N , содержащий неотрицательные целые числа, задача состоит в том, чтобы найти последний оставшийся элемент после выполнения следующих операций (N – 1) раз:

• Отсортируйте массив в порядке возрастания.
• Замените каждый элемент arr[i] на arr[i + 1] – arr[i] для i в [0, N – 2] .
• Удалите последний элемент, arr[n-1] .

Примеры:

Input: arr[] = {5, 2, 1}, N = 3 
Output: 2
Explanation:
1st Operation:  Sorting: arr[] = {1, 2, 5}
                        Replacing: arr[] = {1, 3}
2nd Operation: Sorting: arr[] = {1, 3}
                         Replacing: arr[] = {2}

Input: arr[] = {6, 5, 2, 3, 9, 10}, N = 6
Output: 1
Explanation: 
1st Operation: Sorting: arr[] = {2, 3, 5, 6, 9, 10}
                       Replacing: arr[] = {1, 2, 1, 3, 1}
2nd Operation: Sorting: arr[] = {1, 1, 1, 2, 3}
                        Replacing: arr[] = {0, 0, 1, 1}
3rd Operation: Sorting: arr[] = {0, 0, 1, 1}
                        Replacing: arr[] = {0, 1, 0}
4th Operation: Sorting: arr[] = {0, 0, 1}
                        Replacing: arr[] = {0, 1}
5th Operation: Sorting: arr[] = {0, 1}
                        Replacing: arr[] = {1}
Therefore, the final answer is 1.

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

• Запуск цикла ( N – 1) раз
  • На каждой итерации сортируйте массив.
  • Затем замените каждый arr[i] на arr[i+1] – arr[i] для 0 <= i <N-1 .
  • Уменьшить N на 1.
• Вернуть последний оставшийся элемент.

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

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

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

Suppose, that after the K^th operation, there are p non zero elements, arr[i] ≤ arr[i + 1] ≤ arr[i + 2] ≤ ….. ≤ arr[p – 3] ≤ arr[p – 2] ≤ arr[p – 1].

• Then, after the (K- 1)^th operation, before the array was sorted again, there were p non zero elements, which are, at the minimum, arr[i] ≤ arr[i + 1] + arr[i] ≤ arr[i + 2] + arr[i + 1] + arr[i] ≤ …….. ≤ arr[i] + . . . + arr[p – 1]. This is because, these would have to be the minimum elements for their resultant differences to be same as after the K^th operation. This uses the concept of calculation of prefix sums.
• It can observed that the number of elements that are 0 would increase after each successive operation. For large values of N, the elements of the original array would have to be incredibly large for there to be many non-zero elements. 
• The zero elements would not change due to the operations performed, so we can improve the naive approach by keeping the track of the zero elements, and performing the operations on the rest of the elements.

Примечание. Этот подход не всегда эффективен. Это условие эффективно работает только тогда, когда количество нулей в массиве значительно больше.

Выполните следующие шаги, чтобы реализовать наблюдение:

• Инициализируйте переменную (скажем, zeroCount ) для хранения количества нулей.
• Пройдите массив для выполнения ( N-1 ) операций:
  • Отсортируйте массив.
  • Возьмите один вектор для временного хранения массива на каждом шаге (скажем, ModifiedArr ).
  • Если zeroCount > 0, то уменьшите его на 1 и поместите arr[0] (который будет равен 0) в ModifiedArr .
  • Пройдитесь по массиву:
    • Если arr[i] = arr[i+1] , то увеличить zeroCount на единицу.
    • В противном случае нажмите arr[i+1] – arr[i] в ModifiedArr.
  • Сделать обр = ModifiedArr.
• Если zerCount > 0, возвращается 0.
• В противном случае верните arr[0] .

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

Временная сложность: O(N*M*logM), где M — количество максимальных ненулевых чисел [M = N в худшем случае]
Вспомогательное пространство: O(1)