optimize the python for loop

Question

I have a problem where I need to find the number of unique numbers. No digits in the number would have been repeated.

Number like 11, 1123, 41124 wont qualify. Numbers should be 1234, 12, or 987 like these would qualify. My code works fine. But when the range go beyond 10^6. The code takes lots of time to execute. How can I optimize the same.

for i in xrange(10000000):# pow(10, n) 10, 100, 10000,...
    j = str(i)
    if j != j[::-1]:
        for k in range(len(j)):
            if j.count(j[k]) == 1:
                if k == len(j)-1:
                    count += 1
                    #print j
            else:
                break
    if len(j) == 1:
        count += 1


print count

(1.) Stop using names like i, j, k -- it's very hard to keep up with what is what. (2.) Stop using range(len(j)) and such. It's just going to cause off-by-one errors and make things more difficult to read later (j.count(j[k]). (3.) Use collections.Counter for tasks like this. — Two-Bit Alchemist
– Two-Bit Alchemist, Commented Jun 15, 2016 at 16:49
This isn't something to brute force. You need to do some math to solve this. — user2357112
– user2357112, Commented Jun 15, 2016 at 16:51
contains_repeated_digits = lambda n: any(v > 1 for v in Counter(str(n)).values()) Don't use lambda. It's just an example. — Two-Bit Alchemist
– Two-Bit Alchemist, Commented Jun 15, 2016 at 16:52

kindall · Accepted Answer · 2016-06-15 17:10:36Z

You are going about this in possibly the least efficient way possible, and the longer the number gets, the longer it will take. Your code should look more like this:

for i in xrange(10000000):
    j = str(i)
    if len(set(j)) == len(j):
       count += 1
       # print j

print count

This takes advantage of the fact a Python set can't contain duplicates (duplicates are eliminated). So, if the length of the set of the digits in the number is the same as the length of the original string of digits, we know no digits were duplicated.

You can even write it in one line:

print sum(len(set(j)) == len(j) for j in (str(i) for i in xrange(10000000)))

Others have suggested collections.counter which is useful if you want to know which digits were duplicated.

Psh, give me an afternoon. I can write something way less efficient than OP!

Collectives™ on Stack Overflow

optimize the python for loop

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related