Количество способов выбрать K маленьких четных чисел слева от каждого элемента в заданном массиве

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

Примеры:

Input: arr[] = {4, 2, 12, 33}, K = 2
Output: 0 0 1 3
Explanation: 

1. For arr[0](=4), there are 0, even elements less than arr[i]. Therefore, ways of selecting 2 elements from 0 element is equal to C(0, 2) = 0.
2. For arr[1](=2), there are 0, even elements less than arr[i]. Therefore, ways of selecting 2 elements from 0 element is equal to C(0, 2) = 0.
3. For arr[2](=12), there are 2, even elements less than arr[i]. Therefore, ways of selecting 2 elements from 2 elements is equal to C(2, 2) is 1.
4. For arr[3](=33), there are 3, even elements less than arr[i]. Therefore, ways of selecting 2 elements from 3 elements is equal to C(3, 2) is 3.
    

Input: arr[] = {1, 2, 3}, K = 2
Output: 0 0 1 

Наивный подход: самый простой подход состоит в том, чтобы пройтись по массиву и для каждого элемента найти все числа, которые меньше заданного элемента и даже слева, и проверить, меньше ли число, чем K, а затем вывести 0 , иначе, использовать комбинаторику, чтобы найти количество способов.

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

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

• Инициализируйте упорядоченный набор, скажем, S , чтобы сохранить четные значения.
• Кроме того, инициализируйте массив, скажем, ans[], для хранения результатов.
• Перейдите массив arr[] с помощью переменной i и выполните следующие шаги:
  • Если размер множества S равен 0 , то присвойте 0 элементу ans[i] и продолжите.
  • Найдите количество элементов меньше, чем arr[i] , используя функцию order_of_key() в наборе S , и сохраните его в переменной, скажем, count .
  • Теперь присвойте ответу ans[i] количество способов выбора K элементов из числа i, e C(count, K) .
• Наконец, после выполнения вышеуказанных шагов выведите массив ans[i].

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

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