Сортировать данный массив в соответствии с заданными условиями

Учитывая массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы отсортировать массив таким образом, чтобы –

• Все четные числа должны стоять перед всеми нечетными числами.
• Все четные числа, которые делятся на 5, должны идти первыми, чем четные числа, не делящиеся на 5.
• Если два четных числа делятся на 5, то первым будет число, имеющее большее значение
• Если два четных числа не делились на 5, то первым будет число, имеющее больший индекс в массиве.
• Все нечетные числа должны идти в относительном порядке, поскольку они присутствуют в массиве.

Примеры:

Input: arr[] = {5, 10, 30, 7}
Output: 30 10 5 7
Explanation: Even numbers = [10, 30]. Odd numbers = [5, 7]. After sorting of even numbers, even numbers = [30, 10] as both 10 and 30 divisible by 5 but 30 has a larger value so it will come before 10.
After sorting A = [30, 10, 5, 7] as all even numbers must come before all odd numbers.

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

• Создайте три вектора, скажем, v1 , v2 , v3 , где v1 хранит число, которое является четным и делится на 5 , v2 хранит число, которое является четным, но не делится на 5 , а v3 хранит нечетные числа.
• Повторите в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги:
  • Если arr[i]%2 = 0 и arr[i]%5=0 , тогда вставьте arr[i] в v1 .
  • Если arr[i]%2 = 0 и arr[i]%5 != 0, тогда вставьте arr[i] в v2 .
  • Если arr[i]%2 , тогда вставьте arr[i] в v3 .
• Отсортируйте вектор v1 в порядке убывания.
• После выполнения вышеуказанных шагов выведите вектор v1 , затем выведите вектор v2 , а затем v3 в качестве ответа.

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

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