Максимизируйте разницу в остатках между двумя парами в заданном массиве

Для заданного массива arr[] размера N задача состоит в том, чтобы найти 4 индекса i, j, k, l таких, что 0 <= i, j, k, l < N и значение arr[i]%arr[j ] – максимальное значение arr[k]%arr[l] . Выведите максимальную разницу. Если его нет, то выведите -1.

Примеры:

Input: N=8, arr[] = {1, 2, 4, 6, 8, 3, 5, 7}
Output: 7
Explanation: Choosing elements 1, 2, 7, 8 and 2%1 – 7%8 gives the maximum result possible.

Input: N=3, arr[] = {1, 50, 101}
Output: -1
Explanation: Since, there are 3 elements only so there’s no possible answer.

Наивный подход: Идея грубой силы состояла бы в том, чтобы проверить все возможные комбинации, а затем найти максимальную разницу.
Временная сложность: O(N ⁴ )
Вспомогательное пространство: O(1)

Эффективный подход: Идея основана на наблюдении, что при сортировке массива в порядке возрастания выберите первую пару слева, т. е. минимум 2 значения, и вторую пару справа, т. е. максимум 2 значения. дает ответ. Кроме того, arr[i+1]%arr[i] всегда меньше, чем равно arr[i]%arr[i+1]. Таким образом, минимизируйте значение первой пары и максимизируйте значение второй пары. Выполните следующие шаги, чтобы решить проблему:

• Если размер массива меньше 4, то вернуть -1.
• Отсортируйте массив arr[] по возрастанию.
• Сначала инициализируйте переменную как arr[1]%arr[0] , а затем как arr[N-2]%arr[N-1].
• После выполнения вышеуказанных шагов выведите в качестве ответа значение second-first .

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

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