Given a set S of digits [0-9] and a number n. Find the smallest integer larger than n (ceiling) using only digits from the given set S. You can use a value as many times you want.
For example, d=[1, 2, 4, 8] and n=8753 then return 8811. For, d=[0, 1, 8, 3] and n=8821 then return 8830. For d=[0, 1, 8, 3] and n=8310 then return 8311.
As we know two numbers are equal when all their digits are same in respective positions. The smallest number greater than a number n must have at least one digit greater than its respective position and all the positions right to this position must contain the smallest digits possible.
For example, d=[0, 1, 8, 3] and n=8821 then as long as the digits match from MSB to LSB position we have the numbers matching. For example, [88]. If at a position we don't find the digit in the given digit, for example 3 at position 2 of n, then we want to replace this with the next higher number from the digits d. The next higher digit in this case is 3. Once we find a higher digit we need to have the rest of the digits in the LSBs from this position as smallest as possible i.e. the smallest one. For example, in this case the rest of the position will be filled with smallest digit in d which is 0. So, final answer is 8830.
Question is how to get the next higher digit? We can simply sort the digit array and use binary search to get the floor (smallest number greater than or equal to key) from the array. However there is a special case when all the digits in the given number is contained in the digit. In this case we will end up in generating the input number itself as the next greater number (why?). How to solve this issue? If we do not find a higher digit in the whole scan then we need to replace the LSB of the number by the smallest digit that is strictly higher than the current digit at that position (why?).
Read full article from Find Next Greater Number Using Given Set Of Digits - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment