I applied brute force mechanism in this question and it worked. But is there any better solution for it(like what if the value would have been large)?
Thanks in advance.
It’s obvious that the answer for numbers, which are in form 10^k-1 is 10^k+1.
Number from the input : l
Let’s call number of digits of l : k
For all other numbers next palindrome have
the same number of digits (all numbers that have more digits are greater than 99…99 (k nines),
which is also some solution, but maybe not optimal).
Now, we know that the optimal solution have k digits.
The optimal solution must be in the following form :
some prefix of digits of l + digit greater than the digit on the same position in l + something
Now if the first halfs (maybe plus one digit if odd number of digits) of l
and optimal solution are equal, than the rest of this
solution is known (because optimal solution is palindrome, that’s obvious).
So check if it’s greater than l, and if it is just return it.
for example :
l = 1337321
solution = 1337331 (331 because 133 was at the beginning)
Else (we are searching for the solutions, which have the first half not equal to the first half of l)
for example :
1337321
The result is : 1338331, because all other solutions have the first greater digit, int the lower positions.
Of course 1338331 is greater than 1337331, but it is optimal in this set of solutions(which have the first half not equal to the first half of l).
Here we have just changed the first digit from left from the first half(maybe +1 if k is odd) by one.
But sometimes, we can’t do that, because the digit can be 9, which cannot be changed to greater.
So we continue searching left for the first digit, that is not 9.
Few examples :
l = 184327
if the first half is the same, the solution is 184481, and we stop searching because it is the best solution.
l = 189999
if the first half is the same, the solution would be 189981, but it is not greater than l, so we continue searching : we can’t change the third position, because it’s 9, but second is 8 so we just change it to 9 and the solution is 199991
Hope it helps.
Anyone understand ?
1 Like