Минимальные группы для разделения массива таким образом, чтобы их разница значений каждой пары и разница позиций были одинаковыми.

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

Примеры:

Input: arr[] = {30, 32, 44, 31, 45, 32, 31, 33}
Output: 3
Explanation:
The one possible way to split the array is:

• First group: {30, 31, 32, 33}
• Second group: {31, 32}
• Third group: {44, 45}

Therefore, the number of groups is 3, which is the minimum number of groups in which the array can be split satisfying the conditions.

Input: arr[] = {1, 5, 3, 1, 7, 7, 9}
Output: 7

Наивный подход. Самый простой подход — разбить массив на K подмножеств для каждого целого числа K , меньшего или равного N , а затем проверить, удовлетворяют ли все подмножества заданным условиям или нет. Если окажется, что это правда, то выведите минимально возможный размер раздела.

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

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

• Отсортируйте заданный массив в порядке возрастания.
• Инициализируйте карту, скажем, mp для хранения частоты элементов массива.
• Инициализируйте переменную, скажем, count как 0 , чтобы сохранить количество сформированных непересекающихся групп.
• Пройдите по заданному массиву arr[] и увеличьте частоту каждого элемента в карте mp .
• Пройдите по заданному массиву arr[], используя переменную i , и выполните следующие шаги:
  • Если количество arr[i] в карте mp не менее 1 и количество (arr[i] – 1) в карте mp , тогда:
    • Увеличьте значение count на 1 .
    • Повторяйте до тех пор, пока счетчик arr[i] в mp не станет больше 0 , и на каждой итерации уменьшайте mp[arr[i]] на 1 и увеличивайте arr[i] на 1 .
• Наконец, после выполнения вышеуказанных шагов выведите значение счетчика в качестве ответа.

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

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