I'm working through "Competitive Programming 4" by "Halim et al." and in the topic "Greedy algorithms", I was solving the following problem on Kattis: fridge. The goal of the problem is, given a series of numerals, find the smallest (strictly positive) number you cannot make using each numerals at most once. For example: with these numerals 7129045863, the first number you can't make is 11. For these numerals 55 the first (positive) number you can't make is 1. I implemented the following algorithm: digits = list(map(int, input())) # counting the digits into a dictionary count_0 = 0 dict = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0} for digit in digits: if digit != 0: dict[digit] += 1 else: count_0 += 1 # finding the smallest digit which has the smallest count min_key = 1 min_val = dict[1] for digit, val in dict.items(): if val < min_val: min_val = val min_key = digit if val == min_val and digit < min_key: min_key = digit # printing the result if count_0 + 1 <= min_val: result = int("1"+"0"*(count_0+1)) else: result = int(str(min_key) * (min_val+1)) print(result) The algorithm is based on the fact that amount of 0's should be treated differently then the other digits. When there are plenty of 0's and for example 2 has the least occurrence, then the smallest number you can't form looks like 22...22. If 0 has the least occurrence, the smallest number you can't form looks like 100...0. This algorithm works and passes the time limit test of Kattis. I also tried an algorithm which counts all natural numbers until a number can't be formed, but that fails due to "time limit exceeded". This style of algorithm seems to me more like a greedy approach? So my question is: why would the algorithm above be considered greedy? (if it is to be considered a greedy algorithm). If not, is there a greedy algorithm and what would the greedy approach be? Continue reading...
