What about Time Constraints?

I can give you a solution for a simplified version of this problem (where n,k <= 1e9).

First of all, let's define num[x] as the number of stepping numbers no greater than x. If we were to find a fast enough approach to find num[x], then the problem would be simplified to "Binary Search"; if num[mid]-num[N-1] < K, then the answer is greater than mid, otherwise it's less than or equal to mid. You can start the binary search with l = N and r = 1e18 (as I suppose the answer should be less than 1e18). How to find num[x] quickly? Here, you need to use "Dp On Digits". Let's say we want to find num[mid] where mid = m1m2m3m4...mk (k is the number of digits). To find some stepping number s1s2s3s4...sk where S <= mid, you need to firstly choose s1 so that s1 <= m1, then s2 which has three options: s1-1, s1 and s1+1, and if s1 equals m1, then s2 must fulfill s2 <= m2 (So that the condition S <= mid still holds), otherwise there is no other constraint. Then you continue moving along the digits up till sk (Numbers with less than k digits will also be counted as we are allowing for the option of starting with some arbitrary number of leading zeros). As a result, we only care about three things:

• the digit i were we are choosing si: (1 <= i <= 19)

• j the previously chosen digit (or -1 if i equals 1): (-1 >= j <= 9)

• A boolean number (i.e a flag) k, where k = 1 if we still should care about maintaining (si <= mi), and k = 0 otherwise.

Now we could say that dp[i][j][k] is the number of the remaining choices of the last k-i+1 digits of S if j represents out last choice of a digit, and k represents our situation regarding maintaining the condition (si <= mi). Then, num[x] = dp[1][-1][1]. Note that dp[i][j][k] is different for every number x. Total time Complexity: O(19 * 11 * 2 * log2(1e18)).

The problem with the constraints of yours is that I am not sure that the answer would always fit in a 64-bit integer. If it does, then this given approach should solve the whole problem. You can verify that by finding the answer for N = 1e18, K = 1e18, but use r = MAX_LONG_LONG instead (the maximum value that can be stored in long long variable)