Pages

CodeEval Following Integer

Given a number, we should return its follower, accordingly to a weird rule explained on the CodeEval page of this problem. In a few words, we can only use the digits in the number itself, but we can add a zero if we need to.

The provided samples, that I converted to Python tests, give a better idea of our task:
def test_provided_1(self):
    self.assertEqual(151, solution('115'))

def test_provided_2(self):
    self.assertEqual(2048, solution('842'))

def test_provided_3(self):
    self.assertEqual(80000, solution('8000'))
115 is followed by 151. All the other permutations of the three digits are higher than that.
There is no permutation of 842 that is bigger than it. So we need to add a zero, getting 2048.
Same goes for 8000, we have to add a zero getting 80000.

I felt it was too complicated to check the number and trying to build its follower considering its digits, and I went instead for an almost brute force approach that comes naturally from watching the test case. Check the permutations, and see which one is the next one. If there is no next one, add a zero to the number in second position and return it.

I implemented this algorithm in Python3 adding just a tiny variation. First I generate the number with an added zero and then I check all the permutations. The reason for this inversion should be clear following the code.
digits = []
for c in line:  # 1
    if c != '0':
        insort(digits, c)  # 2
while len(digits) <= len(line):  # 3
    digits.insert(1, '0')
result = int(''.join(digits))
1. Loop on the digits of the passed number, stored in the string named line.
2. I store all the digits but the zeros, sorted in natural order, in the buffer list named digits. The insort function comes from the bisect package.
3. Then I push in the buffer all the required zeros after the first, lowest, significative digit. In this way I get the smaller possible number having one cipher more than the passed one.

Now I am ready to loop on all the permutations for the passed number:
current = int(line)
for item in permutations(line):
    candidate = int(''.join(item))  # 1
    if result > candidate > current:  # 2
        result = candidate
1. I get a permutation, I convert it to an integer. See the itertools library for details.
2. If the current candidate is less than the tentative solution and it is bigger that the number passed in input, I discard the previous calculate result and keep the current one.

At the end of the loop I have in result my solution.

I feared that this intuitive algorithm was too expensive. Fortunately, I was wrong. It has been accepted with good points. Test case and python3 script are on GitHub.

No comments:

Post a Comment