Count how many occurrences of one number there are in another, recursively

Question

Using Python, write a recursive function that determines how many times a number k 2-digit occurs in a natural number n. For example, the number 21 occurs twice in 2135219877.

The problem with my code is that it only counts the two-digit number when there are only two digits in the number being evaluated. How can I fix this?

def verifica(num,c,aux):
    if num==0:
        return c
    
    else:
        if aux==(num//10):
            c+=1
            num=num//10
            return verifica(num,c,aux)
        else:            
            num=num//10
            return verifica(num,c,aux)
    print('numero',aux,'encontrado',c,'vezes')

c=0    
num=int(input('digite um numero: '))
aux=int(input('digite o numero que procura: '))
verifica(num,c,aux)
print('encontrei',aux,c,'vezes.')

Answer 1

Just for the record, recursion is not the most efficient way to solve this problem. That said, let’s go to the solution.

---

One of the problems with your job is that I can call you that: verifica(num, -190, aux) and ready, already messed up the count, because the counter will start at -190. If the counter should always start at zero, it should not be a parameter.

The basic idea of the algorithm is:

• compare the last 2 digits of the number n, if they are equal to k, increment the counter
• divided n by 10 (thus eliminating the last digit) and continue counting
• if n zero, end of algorithm

Assuming the number k always has 2 digits (since this is not verified), would be like this:

def verifica(n, k):
    if n == 0:
        return 0

    if n % 100 == k:
        c = 1
    else:
        c = 0
    return c + verifica(n // 10, k)

n, k = 2135219877, 21
print(f'O número {k} ocorre {verifica(n, k)} vezes no número {n}')

As a return returns the value and closes the execution of the function, the block else in the first if is unnecessary. I also took the print from within the function, because it should only return the value, and whoever the flame does what they want with it (including printing, if applicable). Not to mention that, because it is recursive, several calls are made (one for each digit of n) and there would be printed several messages, unnecessarily.

To get the last 2 digits of n, just take the rest of the split by 100, using the operator %. Then I’ll see if it equals k, and we are 1 if applicable.

Then this value is summed with the result of the count on the remainder of the number (the result of the division of n by 10).

It is worth remembering that verifica(111, 11) returns 2, because the last two digits of 111 are 11, and then I divide 111 by 10, resulting in 11, which accounts for another occurrence of 11.

---

As already said, the algorithm works only if k has exactly 2 digits (or if it is less than 10, for example, if n for 10303 and k for 3, the count counts 2).

But if the idea is to make the algorithm more "generic", you can check the number of digits of k and use this value in the calculation - generally, if k has x digits, just take the rest of the split by 10^x.

Another detail is that you don’t have to go to n be equal to zero. If n is less than k, I can stop the check now, because then there will be no further occurrence:

import math

def qtd_digitos(numero):
    numero = abs(int(numero))
    return (1 if numero == 0 else math.floor(math.log10(numero)) + 1)

def verifica(n, k):
    if n < k:
        return 0
    if n % (10 ** qtd_digitos(k)) == k:
        c = 1
    else:
        c = 0
    return c + verifica(n // 10, k)

---

Remember that the recursive solution is not ideal for this case. This is because many recursive calls can cause a pile burst if the number of calls is large enough.

In that case, a loop simple already solves. Also, missing check some corner cases, when both values are zero, or when only k is zero:

import math

def qtd_digitos(numero):
    numero = abs(int(numero))
    return (1 if numero == 0 else math.floor(math.log10(numero)) + 1)

def verifica(n, k):
    if n == 0 and k == 0:
        return 1
    c = 0
    qtd = qtd_digitos(k)
    while (k == 0 and n > k) or (k != 0 and n >= k):
        if n % (10 ** qtd) == k:
            c += 1
        n //=10
    return c

print(verifica(0, 0)) # 1
print(verifica(100, 0)) # 2