I just want a direction in this programming problem from an online judge (URI online judge - 2699). Given two numbers, S and N, S is incomplete, so S can be given in the form ?294?? where the first digit is not zero, I need to find the minimum number that has the same digits as S and is multiple of N. If is not possible, then you just return a *. S can have up to 1000 digits and N < 1000.
I will describe my attempts:
Brute Force: I try every combination of numbers and get the first one to be multiple of N. Finding a solution when it exists is not the problem at all, but discovering that does not exist a solution when S is big can be really problematic and take infinite time.
Brute Force but optimizing the form of finding the rest: This attempt i save into an array the rest of the division for the digit 1 in the i position, so for i = 3, in v[3] i will have 1000%N. Knowing that (AB) MOD N = ((A MOD N)B) MOD N it's possible to write an array pretty quick and optimize the way i calculate the Mod of S which. This attempt does improve the time but is a Brute Force Attempt and has the same issues that the previous one.
Using the remainder to do the recursion: Ex: If i have the number ?294?? in S, i get the remainder of 29400 and calculate how much is needed to have a multiple (N - rem), then i try to get it all from the first digit, if it is not possible then i decrease how much I want and try again, then I go to the left and try with another number. Ex if i need 7 to reach N and can get 5 with the first digit, then I will try to find 2 within the second digit and so on.
Does it have a concept that i ain't seeing here ? I'm trying this problem for almost 3 days, searching ways to do this and not getting anywhere because of time.
EDIT: Thanks for the comments, after thinking all day about this problem and reading a lot of Dynamic Programming I could figure a way to apply DP in this problem, I won't say exactly how but the key is to understand DP and figure a way to reduce the size of your problem.