Неограниченное количество изменений, чтобы получить равный массив

Question

Чтобы прояснить это, это не домашнее задание, мне задали этот вопрос в недавнем интервью и нарисовали пробел. Так что я следующий массив,

{1, 6, 3, 2, 9} 

изменение является шагом, который увеличивает любой элемент на 1 и уменьшает любой другой элемент на 1. Таким образом 1 изменение может быть как,

{2, 5, 3, 2, 9} 

Я м позволили сделать неограниченное количество таких изменений, пока я получаю максимальное количество одинаковых элементов, таким образом, данный массив может стать

{3, 3, 3, 3, 7} or {3, 4, 4, 4, 4} 

За этой точкой больше изменений не будут получать больше Ele равные. Таким образом, возникает вопрос о неограниченных изменениях, каково максимальное количество элементов, которые могут быть равны. Таким образом, ответ для вышеупомянутого массива 4. (Обратите внимание, есть два случая, в любом случае, хотя ответ 4) Другой пример будет массив,

{1, 4, 1} 

В этом случае мы можем внести изменения, чтобы добраться до

{2, 2, 2} 

Таким образом, ответ в этом случае 3. Может кто-нибудь помочь мне с подходом к началу работы. Я все еще рисую пробел.

Answer 1

Это, кажется, математическая проблема, а не связанная с компьютером. Поскольку каждое «изменение» увеличивает один элемент и уменьшает другой, сумма всех значений в массиве постоянна.

Это означает, что вы можете получить все элементы массива n идентичными тогда и только тогда, когда сумма всех элементов может быть поделена на n. В противном случае один из элементов должен принять другое значение, чтобы получить равные элементы n-1.

Кстати, ваши ответы {3, 3, 3, 3, 7} и {3, 4, 4, 4, 4} (сумма 19) не являются решением вашего предыдущего состояния {1, 6, 3, 2, 9} (сумма 21).