I encountered a algorithm problem:

Given an array arr(just include some single digit num) and a integer K (you can assume int type in java), combine the number in the array to get a smallest integer that larger than K. (Combine means like you can regard every element in arr as a string, and concatenate them. for example: I use four "1"s to get "1" "1" "1" "1" = "1111")

Example:

arr: [1,2,3,4] target:123 , output: 124

arr: [1,2,3,4] target:999 , output: 1111

arr: [9] target:23 , output: 99

I can just came up with a brute force way, using backtracking to find all possible combination first and loop thru the all candidates to find the result.

Any optimization here?

CodePudding user response：

The following set of observations can be used to solve this:

1. For a x digit target, the answer will have either x digits or x 1 digits
2. If the target is greater than the largest x digit number we can generate, the answer will be the smallest x 1 digit number possible. (Example: arr: [1,2,3,4], target:999, output: 1111)
3. Else, we iterate over the digits of the target. For each digit, we find the closest integer in our array which is greater than or equal to the digit. If the chosen digits are equal, we proceed. Else, if our chosem digit is greater, we can greedily insert the smallest possible digit for the remaining places.
   Example: arr: [1,2,4,6,9] target: 12378. Iterating over the target:

Digit: 1, closest value = 1 (which are equal)
Digit: 2, closest value = 2 (which are equal)
Digit: 3, closest value = 4 (which is greater)
Since we've picked a greater value now, we will pick the smallest digit for the remaining places.
Digit: 7, chosen value = 1 (which is the smallest digit we can choose)
Digit: 8, chosen value = 1 (which is the smallest digit we can choose)
Final answer = 12411