Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- mem = dict() #global dictionary for memoization
- def expressible(m,digits,k):
- if (m,digits,k) in mem:
- return mem[(m,digits,k)]
- elif m == 0 and k == 0:
- mem[(m,digits,k)] = True
- return True
- elif len(digits) == 0 or k > len(digits):
- mem[(m,digits,k)] = False
- return False
- else:
- for d in set(digits):
- i = int(d)
- remaining = digits.replace(d,'',1)
- if expressible(m + i,remaining, k-1) or expressible(m - i,remaining, k-1):
- mem[(m,digits,k)] = True
- return True
- #if we reach here:
- mem[(m,digits,k)] = False
- return False
- def selfContained(a,b):
- nums = []
- for n in range(a,b+1):
- digits = ''.join(sorted(str(n)))
- contained = True #until a counter-example found
- for d in set(digits):
- i = int(d)
- remaining = digits.replace(d,'',1)
- if not expressible(i,remaining,2):
- contained = False
- break
- if not contained: break
- #if we reach here and contained is still true, no counterxamples, so:
- if contained: nums.append(n)
- mem.clear()
- return nums
- >>> selfContained(1,360)
- [101, 110, 112, 121, 123, 132, 134, 143, 145, 154, 156, 165, 167, 176, 178, 187, 189, 198, 202, 211, 213, 220, 224, 231, 235, 242, 246, 253, 257, 264, 268, 275, 279, 286, 297, 303, 312, 314, 321, 325, 330, 336, 341, 347, 352, 358]
- nums = selfContained(0,1000000)
- 999909, 999918, 999927, 999936, 999945, 999954, 999963, 999972, 999981, 999990
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement