Find the kth eleven-non-free number

Question

Let's define eleven-non-free numbers:

If we consider a number as a string, then if any substring inside is a (non-zero) power of 11, then this number is an eleven-non-free number.

For example, 1123 is an eleven-non-free number as 11 inside is 11^1. Also 12154 is one as 121 is 11^2. But 12345 is not, because we can't find any non-zero power of 11 inside.

So given a k, find the kth eleven-non-free number. For example the 13th such number is 211.

I don't know how to efficiently do it. the brute-force way is to increase i from 1 and check every number and count until the kth.

I guess we should consider strings with different length (1, 2, 3, 4, ...). then for each length, we try to fill in 11, 11^2, 11^3, etc and try to get all the combinations.

But it seems quite complicated as well.

Anyone?

Answer 1

This looks like an O(klog^2(k)) algorithm:

def add(vals, new_vals, m, val):
    if val < m and val not in vals and val not in new_vals:
        new_vals.append(val)

def kth11(k):
    vals = [ 11**i for i in range(1, k+1) ]
    new_vals = [ ]
    while True:
        vals = sorted(vals + new_vals)
        vals = vals[:k]
        m = vals[-1]
        new_vals = [ ] 
        for v in vals:
            for s in range(1, 10):
                val = int(str(s) + str(v))
                add(vals, new_vals, m, val)
            for s in range(0, 10):
                val = int(str(v) + str(s))
                add(vals, new_vals, m, val)
        if len(new_vals) == 0: break
    return vals[-1]

print kth11(130)

Answer 2

10^18 is really, really big. Brute force is not your friend.

However, let us note some conveniences:

• If a string s represents a eleven-non-free number, then trivially so does d s (where d is a string of digits).
• If you wanted to know how many k-digit numbers are eleven-non-free, you could base that off of how many k-1-digit numbers are eleven-non-free.
• (e.g. how many 1xx numbers are eleven-non-free? Well, how many xx numbers are eleven-non-free? Obviously at least that many 1xx numbers are eleven-non-free.. The only additional cases are when a power of eleven starts with the digit at the start -- with the 1 that just got tacked on the front.)
• This suggests a relatively straightforward dynamic programming approach to figure out how many eleven-non-free numbers are in a string of known length with a fixed prefix. (e.g. how many eleven-non-free numbers are in 934xxxxx)

Finally, throw some binary-search style logic on top, and you should be able to find exactly which number is the N-th eleven-non-free number.