Во-первых, в вашем алгоритме цикл while вообще не нужен. Сколько нужно операций +1, чтобы из a получить a+12345? Ровно 12345. Вам надо просто вычесть одно число из другого.
Далее, мысль должна быть такая: Вот вы знаете, сколько нужно операций, чтобы все числа в массиве привести к X. Вопрос: сколько операций вам понадобится для приведения всех чисел к X+1? (Подсказка - если число было меньше X, то теперь понадобится на 1 операцию больше. Если число было больше X - то понадобится на 1 операцию меньше).
Теперь вам надо посмотреть, подумать и выбрать оптимальное X, которому вы будете приводить все числа. Ваш вариант с max/2 не оптимален.
