Для начала заметим, что наиболее выгодно заменять цифры на 9. При этом, логично, что не нужно заменять 9-ки.
Дальше заметим, что чем больше разряд, тем выгоднее его заменить, так например, в числе 85 выгоднее заменить 8-ку, чем 5-ку.
Еще один полезный факт — понять, что в одинаковых разрядах выгоднее заменять меньшую цифру. Данный факт можно было понять из первого примера в условии.
Чтобы решить задачу, нужно преобразовать число в сумму разрядных слагаемых. Для примера 123 = 100 + 20 + 3 = 1·102 + 2·101 + 3·100. Положим все такие слагаемые в массив, задавая их парой из цифры и степени 10-ки: {(1, 2), (2, 1), (3, 0)}.
И наконец, отсортируем этот массив, сначала по уменьшению степеней 10-ки, а потом по увеличению цифры, и выбрать первые k элементов. Для каждой пары (x, y) к ответу прибавим (9 - x) * 10y.
P. S. Можно сразу положить в массив (9 - x) * 10y и сортировать уже такие числа.