Проверить, можно ли переставить данный массив так, чтобы среднее значение равнялось медиане

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

Примеры :

Input: arr[] = {1.0, 3.0, 6.0, 9.0, 12.0, 32.0}
Output: Yes
Explanation: The mean of given array is (1.0 + 3.0 + 6.0 + 9.0 + 12.0 + 32.0) / 6 = 10.5. 
Rearranging given array as {1.0, 3.0, 9.0, 12.0, 6.0, 32.0}, here median is (9.0 + 12.0) / 2 = 10.5

Input: arr[] = {8.0, 13.0, 15.0}
Output: No

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

• Инициализируйте переменную, скажем, для хранения среднего значения arr[] .
• Проверьте, является ли размер arr[] четным или нечетным.
  • если размер arr[] четный
    • Используйте подход с двумя указателями для поиска двух элементов, среднее значение которых = среднее .
    • Инициализируйте два указателя как i=0, j=n-1 .
    • Выполните подход с двумя указателями для поиска медианы в arr[] .
  • если размер arr[] нечетный
    • Примените двоичный поиск, чтобы узнать, присутствует ли среднее значение в arr[] или нет.
• Если среднее значение найдено, верните Да , в противном случае Нет .

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

Временная сложность : O(N), когда N четно.
O(logN), когда N нечетно.
Вспомогательное пространство : O(1).