Problem statement

Here is the Link to the problem

We need to find any number in the range $$$[l, r]$$$ with the least luckiness

Luckiness of a number is defined as the difference between its maximum and minimum digit

So for $$$n = 369$$$ the luckiness will be 9 — 3 = 6

Solution

Basic Idea

So for a number $$$n$$$ let the min and max digit be $$$m$$$ and $$$M$$$ respectively, we need to find n with the least value of $$$M - m$$$

1. Since we want to minimize this difference, we can iterate over the differences in the range $$$[0, 9]$$$
2. We can then choose the smallest digit $$$m$$$ for our number in the range $$$[0, 9]$$$
3. Then, $$$M$$$ = $$$m + diff$$$

So we need to just check if there exists a number in the range $$$[l, r]$$$ such that all its digits are greater than equal to $$$m$$$ and less than equal to $$$M$$$. Also not forgetting that at least one digit must be $$$m$$$ and atleast one digit must be $$$M$$$ to get $$$diff = M - m$$$

Calculation of Predicate function

Lets define $$$count$$$$$$(n, m, M)$$$ as the count of non negative numbers $$$\le n$$$ whose digits lie in the range $$$[m, M]$$$

To find the count function we can iterate over the digits of n.

Say we are the $$$i^{th}$$$ digit from the left where we will have 2 choices

1. Either to select a digit lesser than $$$d[i]$$$
   • In this case we will have all the options from $$$[m, min(M, d[i] - 1)]$$$
   • Since we have selected a smaller digit remaining positions can be filled by any digit in $$$[m, M]$$$
2. Or we an simply select $$$d[i]$$$ and look for possibilities in the remaining number

If we see this count will also include those numbers which won't have digits $$$m$$$ and $$$M$$$ together, where all the digits are either in the range $$$[m + 1, M]$$$ or $$$[m, M - 1]$$$.

We need to remove those numbers from our count to get a $$$netCount(n, m, M)$$$ which gives the count of all the numbers which have atleast one digit $$$m$$$ and atleast one digit $$$M$$$ and all remaining digits satisfy the range $$$[m, M]$$$

You can try some example cases to get why this thing works.

To check if such a number $$$\ge l$$$ and $$$\le r$$$ exists we can simply check using a predicate function $$$get$$$

Binary Search Part

After finding the optimal $$$m$$$, $$$M$$$, optimal $$$diff$$$ by iterating over the possible differences in the first part and checking if they satisfy the predicate function, we can use binary search.

Since $$$netCount$$$ is monotone (non decreasing function in our case),

We can find the first number in the range $$$[l, r]$$$ using binary search which satisfies the $$$get$$$ function and this will be our final answer which will have all the digits $$$\ge m$$$ and $$$\le M$$$ and the least difference $$$M-m$$$

With this binary search approach, i think we can even find $$$k^{th}$$$ smallest number with the optimal difference. You can try solving for that task

Here is the accepted submission

Finding kth smallest number with any difference

code which finds minimum number with least difference

code which finds median number with least difference

code which finds largest number with least difference

Thanks for reading my blog, have a great day :)