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.
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
else intCheck(y // 10, x) in your program where the bug exists. the problem is x is x // 10 after intCheck recurs, so there's no way to go back and check the original x against y // 10.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.
True for intCheck(1234567,125) and intCheck(1234567,2347)else intCheck(y // 10, x) in your program where the bug exists. the problem is x is x // 10 after intCheck recurs, so there's no way to go back and check the original x against y // 10.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.
x: if 99 < x < 10: return 'Invalid' as the orig. PO stated?
(y,x) (based on what our school uses to check our codes).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
12in132OK)? For the record, recursion is a horrible solution to this problem. Your teacher is telling you to hammer a nail and giving you a feather, a hairpin and a pipe cleaner to do it with. You can just usestr(x) in str(y), so don't let your teacher get in the way of your education.(y, x), just like in the code, so in my examples, it just says that, for example 1,23is in1234, while in example 2,44is not in76384. And yeah, I figured that using recursion in this problem is hard, but we'll get a zero grade if we don't use recursion so we have no choice :(str(x)compare withstr(y)as @ggorlen suggested. Because number can only be compared with ordinal values.