### fun.contest.id's blog

By fun.contest.id, 2 months ago, ### Problem statement

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$

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] netCount(n, m, M) = \ count(n, m, M) — count(n, m + 1, M) — count(n, m, M — 1) + count(n, m + 1, M — 1) 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 get(l, r, m, M) = netCount(r, m, M) - netCount(l -1,m, M) > 0 #### 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 :)  Comments (15)  » well, thats preaty neat solution, definitely better than mine)) I used 6D dynamic programming approach •  » » 6D :O. I get confused if they are beyond 3 dp states. Thanks btw  » 2 months ago, # | ← Rev. 2 → Interesting. I came up with the BS approach too and finding the kth term for a minimum and maximum digit took me time to arrive at.I am pretty sure I have seen the concept in some past div 3 / 2 before. •  » » 2 months ago, # ^ | ← Rev. 2 → Yes if we can somehow calculate count function, we can always use binary search because having more numbers won't decrease count, it will either remain same or increase. I remember an interactive problem asked in Atcoder contest where we need to determine the position of a rook with some properties.  » 2 months ago, # | ← Rev. 2 → Why have u used this ? if(a != 0 and l > 1) if(options > 1) res += options * (binexp(options, l - 1) - 1) / (options - 1); else res += l - 1; if(self) res++;  •  » » All the numbers with digits lesser than those of n can be filled in any order with options available [m, M]. So we do (options)^{l-1} + (options)^{l - 2} +........ options^{1}If you see this is a geometric progression with a = options, r = options, cnt = l - 1This sum will be equal to \displaystyle a\left(\frac{r^{cnt} - 1}{r - 1}\right)Just substitute corresponding a,r, cnt in the function. Also we need to handle some cases when l = 0 or r = 1 or minimum_digit = 0 •  » » » Ohh right, understood !!! Just 2 more question.1 — for options == 1, why have u added l-1 . All the digits must be same so order should be insignificant2 — What is if(self) res++; used for ? •  » » » » 2 months ago, # ^ | ← Rev. 2 → let say n = 123456, a = 2, b = 2, so we have only 1 choice i.e placing 2 on every position.So numbers with 5 digits or less will be like 22222, 2222, 222, 22, 2. So i added (l - 1) i.e (6 - 1) = 5 to account for these numbers.This thing is nothing but the part of our gp series only, but we cant use (options - 1) as it will come out to 0 and will give us a runtime error. So we need to simplify it first and it will come out to be 1^{l - 1} + 1^{l-2} +......1^{1} = (l - 1)$$Self$ for if the number itself satisfy the properties
•  » » » » » Now I am clear with each part of the code.Thank u for such neat blog and for being patient. Appreciate it
•  » » » » » » Thanks bro, i am glad you understood and it helped you :)
 » 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] `With numbers with the number of digits less than n starting with the digit 0, how do you handle it?
•  » » U can refer to this comment thread above
 » This solution is actually incredibly smart!
•  » » Thank u ^_^
 » Your solution is witty and artistic. There were numerous base cases which I couldn't think of while analyzing the problem and your code and this post mentions them clearly. The algorithm for count function is genius. Thank you for the blog.