Подсчет всех возможных массивов, в которых каждый элемент массива может находиться в диапазоне [1, arr[i]]

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

Примеры:

Input: arr[] = {5}
Output: 5
Explanation:
All possible arrays that can be formed using the given criteria is {1}, {2}, {3}, {4}, {5}. Therefore, the count of such array is 5.

Input: arr[] = {4, 4, 4, 4}
Output: 24

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

Иллюстрация:

Consider the array arr[] = {1, 2}, every possible array formed satisfying the given criteria is {1, 2}.

Now, if the order of element of arr[] is changed, say {2, 1}, then every possible array formed satisfying the given criteria is {2, 1}.

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

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

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

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