Efficient method to count the numbers that have at least one digit that repeating

user_13354525 0
Viewed 379

I'm trying to find an efficient method to count the number of positive integers less or equal than a certain number x that have at least one digit that repeating.

I tried to count the numbers that have repeating digits and then substract it from x, but my program became too slow for x up to 10^10.

I searched and I found two ways to implement this idea:

def count_unique(x): 
    cnt = 0
    for i in range (x + 1): 
        num = i
        visited = [0,0,0,0,0,0,0,0,0,0]
        while (num): 
            if visited[num % 10] == 1: 
                break
            visited[num % 10] = 1 
            num = (int)(num / 10)
        if num == 0: 
            cnt += 1
    return cnt -1
for i in range(int(input())):
    x = int(input())
    print(x - count_unique(x))

And :

Prefix = [0] 
def repeated_digit(n): 
    a = [] 
    while n != 0: 
        d = n%10
        if d in a: 
            return 0
        a.append(d) 
        n = n//10
    return 1
def pre_calculation(MAX): 
    global Prefix 
    Prefix.append(repeated_digit(1)) 
    for i in range(2,MAX+1): 
        Prefix.append(repeated_digit(i)+Prefix[i-1]) 
MAX = 10000000000
pre_calculation(MAX) 
for i in range(int(input())):
    x = int(input())
    print(x - Prefix[x])

but unfortunately none of them was fast enough, Does anyone have a better way to achieve this?

Sample input:

2    #number of test cases
10
20

Sample Output : (the result for each test case)

0   #no number less than 10 with a repeating digit
1   #one number less than 20 with a repeating digit (which is 11)
algorithm python
3 Answers

You are going through a lot of pain to deconstruct the number and count digits. Let's simplify those steps. Given an integer num, get the individual digits, and then find the unique digits:

digits = str(num)
unique_digits = set(digits)

Now, if there are fewer unique digits than the length of the original number, you have a repetition.

I trust you can handle the coding from here.

user_47851850

I really think the implementation of this wouldnt be worth it unless you are trying to do it a lot times. If its for practice, I think knowing about permutations can be usefull.

What about using permutations and combinations. You see, with permutations, you can count the number of ways you can arrange a certain group of digits, with or without repeating.

Ok, first thing, every number above 10 degits, has a repeated number. So you can skip counting everything above 9,999,999,999

A permutation can give you the count of ways a group has no repeated numbers. Using this and a simple substraction you can find what you want. (you would have to do it for every place value, unit, tens, hundreds...) (Also you would have to eliminate the ones that start in a 0, with another permutation)

Now, the problem with this is it can only count exactly the ones that have only 9s. For example 9999, because it counts all posibilities. lets say you have a 3999, For this you'll have to count the last 3 digits posibilities, without a 3 in the permutation group. Then add the permutation with repetition with a 3 already included. Then repeat for 2999, 1999 and add the posibilities for 999 The reasoning is the following:

  • if you already have a 3 in the first digit, if it appears again is repeated. So if you count the permutations without the 3. Then you can just add up all the permutations that include at least a 3.

With a number like 3244, youll just have to apply the same thing for 244...

I know this is not exactly a simple solution, and it can be confusing, but it could reduce your task for somthing like log(n).

Good luck :)

You can search about permutations on google, its a pretty common thing in math.

user_79222290

I would attempt to analytically find out the compliment of the number and use this value to compute the final result.

Consider (for, N = requested-input):

1. X = #positive-integers with all unique digits
2. Create the algo to figure out X
3. Final result = N - X

Here is my working code:


def all_unique_numbers_with_n_digits(d: int):
    if d < 1:
        return 0
    count = 9
    dig = 9
    while d > 1:
        count *= dig
        dig -= 1
        d -= 1
    return count


def count_numbers_with_unique_digits_less_than_n(n: int):
    X = str(n)
    count = 0

    unique_digs = set(range(9))

    for i in range(1, len(X)+1):
        # print("i,", i, X)
        dig_value = int(X[i-1])
        dv = dig_value if i == len(X) else dig_value-1
        # print(X, i, dig_value, dig_multiplier, count)
        count += max(dv, 0) * all_unique_numbers_with_n_digits(len(X)-i)
        if dig_value in unique_digs:
            unique_digs.remove(dig_value)
        if i != len(X):
            count += all_unique_numbers_with_n_digits(len(X)-i)
        else:
            mval = 0
            for x in unique_digs:
                if dv >= x > mval:
                    mval = x
            count += mval

    return count


def numbers_with_atleast_1_dig_repeating(n: int):
    return n - count_unique(n)


print(count_numbers_with_unique_digits_less_than_n(9))
print(count_numbers_with_unique_digits_less_than_n(100))
print(count_numbers_with_unique_digits_less_than_n(101))

Output:

90
90
90
user_102084810
Related