Да, протупил. Массив на 28 ячеек и сумма в каждой, по окончании прохода — поиск наименьшего (это быстрее, чем находить минимум на каждой итерации)

template<class T>
int less_frequent_sum (T* data, size_t size) {
int sum[28];
for (int i = 0; i < 28; sum [i ++] = 0);
for (int i = 0; i < size; i ++)
sum [sum_of_digits (data [i])] ++;
return min_non_zero (sum);
}