Integer Count Python using Recursion

Question

How can I make a recursive function that determines whether an integer x is part of an integer y? For instance, the function will return True if we input (1234, 23) and False if we input (76384, 44). x can also only be a two-digit positive number. I already did the last condition:

def intCheck(y, x):
    if x < 10 or x > 99:
        return "invalid"

But I don't know how to do the main part of the code.

Answer 1

You can check if the last two digits match using a modulo 100 on N. Then remove the last digit of N and repeat the process. Continue until all digits have been checked:

def numContains(N,x,p10=10):
    if N<0:      return numContains(-N,x)       # remove sign from N
    if N<x:      return False                   # exhausted digits of N
    if p10<=x:   return numContains(N,x,p10*10) # find right decimal scale
    if N%p10==x: return True                    # x matches ending digits
    return numContains(N//10,x,p10)             # remove last digit

print(numContains(12345,23))      # True
print(numContains(76384, 44))     # False
print(numContains(7612384, 123))  # True
print(numContains(-7612384, 123)) # True

If non-consecutive digits (in same order) are eligible, then the function can be altered to remove ending digits at each position within the decimal scale of x:

def numContains(N,x,p10=10):
    if N<0:      return numContains(-N,x)       # remove sign from N
    if N<x:      return False                   # exhausted digits of N
    if p10<=x:   return numContains(N,x,p10*10) # find right decimal scale
    if N%p10==x: return True                    # x matches ending digits
    t=1                
    while t<p10:                                # within range of x's scale       
        left,right = divmod(N,t)                # remove digit near end
        if numContains(left//10*t+right,x,p10): # try with that
            return True
        t *= 10
    return False

print(numContains(7612384, 134)) # True
print(numContains(7612384, 143)) # False
print(numContains(17633333000842222, 134)) # True

Answer 2

Here's a variation that works for inputs of any size. We can use mathematical induction to form logical structure of our program -

def int_check(whole, part):
  if whole < part:
    return False                        # base case: w < p
  elif whole % e(part) == part:
    return True                         # induction: w >= p
  else:
    return int_check(whole // 10, part) # induction: w >= p, w % e(p) != p

def e(n, m = 10):
  if n < 10:
    return m                            # base case: n < 10
  else:
    return e(n // 10, m * 10)           # induction: n >= 10

Here's a variation that does not need to compute a separate e (seen above). This has some similarity to @Morinator's technique but is careful to avoid bugs found in their answer -

def int_check(whole, part):
  def loop (w, q):
    if q == 0:
      return True                        # base case: q == 0
    elif w < q:
      return False                       # induction: q > 0
    elif w % 10 == q % 10:
      return loop(w // 10, q // 10)      # induction: q > 0, w >= q
    else:
      return loop(w // 10, part)         # induction: q > 0, w >= q, w % 10 != q % 10
  return loop(whole, part)

Each implementation of int_check has the same output -

print(int_check(1234567, 23))       # True
print(int_check(1234567, 456))      # True
print(int_check(1234567, 3))        # True
print(int_check(1234567, 123))      # True
print(int_check(1234567, 3456))     # True
print(int_check(1234567, 56))       # True
print(int_check(1234567, 1234567))  # True

print(int_check(1234567, 58))       # False
print(int_check(1234567, 125))      # False
print(int_check(1234567, 2347))     # False
print(int_check(1234567, 45679))    # False
print(int_check(1234567, 99))       # False

Answer 3

Note: In this solution, x needs to be contained as continuous subsequence, i.e. (123, 13) would evaluate to False.

def intCheck(y, x):
    if not 10 <= x <= 99:
        return "invalid"

    if y < 10:  # y is too small to contain x
        return False
    elif (y - x) % 100 == 0:  # x is contained in the last 2 digits of y
        return True
    else:
        return intCheck(y // 10, x)  # check if y is inside the other digits of y => remove last digit of y

Like the comment says though, you shouldn't use this function in real life.

Answer 4

def intCheck(y, x):
    if x == 0:
        return True
    if y == 0:
        return False

    return intCheck(y // 10, x // 10) if (y - x) % 10 == 0 else intCheck(y // 10, x)

This version works in all my tests, according to the new problem definition.