alexalghisi's blog

By alexalghisi, 7 years ago, In English

The approach of this problem is relatively easy.

We take the first number and make it the minimum possible : every ? will be 0 but you must take care of the leading zeroes.

For the next numbers we will always build the next number based on the current number. So after having computed the i'th number we go on and compute the number at i+1 . How ?

Case 1 :

If len(v[i]) < len(v[i+1]) we can easily compute v[i+1] as we have done for the first number "every ? will be 0" ( the minimum number )

Case 2 :

If len(v[i]) = len(v[i+1]) we must find the first difference between the two numbers going from the most significant digit to the less significant one . So if we have :

2
128934
12??35

we take the ?? as 89 + 1 , so our number will become 129034 . By doing so , we will always take the minimum for each number. If we have other question marks after , we should make them 0. For example :

2
1243499324
12???992?3

Our result will be : 12 435 992 0 3

Case 3:

If len(v[i]) > len(v[i+1]) we have no solution.

Lemma: We must always take the minimum for each number .

Proof: Consider an input test like this : n = 10 and after that 10 ? .

In order to be able to compute all this numbers we must take the minimum in each case so the result will be : 1,2,3 ... 10 . There is no other solution .

*len = length = number of digits in this problem

Read more »

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it