Найдите K пропущенных чисел из заданного массива в диапазоне [1, M] так, чтобы общее среднее было X

Дан массив arr[] целых чисел размера N , где каждый элемент может находиться в диапазоне [1, M], и два целых числа X и K . Задача состоит в том, чтобы найти K возможных чисел в диапазоне [1, M] таких, что среднее всех (N + K) чисел равно X. Если есть несколько правильных ответов, любой из них является приемлемым.

Примеры:

Input: arr[] = {3, 2, 4, 3}, M = 6, K = 2, X = 4
Output: 6 6
Explanation: The mean of all elements is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Input: arr[] = {1}, M = 8, K = 1, X = 4
Output: 7
Explanation: The mean of all elements is (1 + 7) / 2 = 4.

Input: arr[] = {1, 2, 3, 4}, M = 6, K = 4, X = 6
Output: []
Explanation: It is impossible for the mean to be 6 no matter what the 4 missing elements are.

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

1. Найдите сумму недостающих элементов (Y), то есть = X*(K + N) – sum(arr).
2. Если это значение меньше K или больше K*M , то массив не может быть создан. Поэтому верните пустой массив.
3. В противном случае попытайтесь разделить значение Y на K элементов поровну, т.е. присвоить всем K элементам значение Y/K.
4. если все еще остается какое-то значение, которое нужно присвоить, то после одинакового присвоения каждому элементу оставшееся значение будет = (Y%K). Поэтому добавьте 1 к (Y%K) элементам нового массива.

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

Временная сложность: O(N)
Вспомогательное пространство: O(1) Когда пространство результирующего списка не учитывается