Maintain an F.S.A to keep track of the consequent remainders as states, input symbols as driving actions on each state. O(N) is the time complexity to find the given large string [in some radix(R), for some specific divisor(D)], where N is the length of the Input String which confirms to the Language Rules under the alphabet. O(R*D) is the space complexity to keep the F.S.A in memory for lookup!
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def infinite_stream_divisor(base, divisor, stream):
k = -1
fsa = {}
for state in range(divisor): # Does the trick :)
fsa[state] = []
for input in range(base):
k = (k+1) % divisor
fsa[state].append(k)
state = 0
for symbol in stream:
state = fsa[state][int(symbol)]
if state == 0:
return True
return False
|
Well, this one needs little more explanation than what was explained. Little understanding of the theory of computation or Finite State Automata theory is enough. Each state(row) holds the remainder upon receiving the input symbol, each symbol(column) represents the target state to change upon the input.
Usage: base = int(raw_input("Enter Number System For the Input Sequence:")) divisor = int(raw_input("Enter the Divisor:")) stream = raw_input("Enter the Sequence:")
if infinite_stream_divisor(base, divisor, stream): print "The string is divisible by ", divisor else: print "The string is not divisible by ", divisor
""" Enter Number System For the Input Sequence:2 Enter the Divisor:3 Enter the Sequence:111 The string is not divisible by 3 """
Related Links: http://en.wikipedia.org/wiki/Divisor_function
Of course, if we can develope a FSA [or NFA, which can be minimized to an FSA], we can write a regex and do it. http://mathforum.org/kb/message.jspa?messageID=4614160&tstart=0 Solution: http://mathforum.org/kb/message.jspa?messageID=7134648&tstart=0
Thanks.