Split a Numeric String into Fibonacci Sequence | Python3 program of the above approach ; Function that returns true if Fibonacci sequence is found ; Base condition : If pos is equal to length of S and seq length is greater than 3 ; Return true ; Stores current number ; Add current digit to num ; Avoid integer overflow ; Avoid leading zeros ; If current number is greater than last two number of seq ; If seq length is less 2 or current number is is equal to the last two of the seq ; Add to the seq ; Recur for i + 1 ; Remove last added number ; If no sequence is found ; Function that prints the Fibonacci sequence from the split of string S ; Initialize a vector to store the sequence ; Call helper function ; If sequence length is greater than 3 ; Print the sequence ; If no sequence is found ; Print - 1 ; Driver Code ; Given String ; Function Call
import sys NEW_LINE def splitIntoFibonacciHelper ( pos , S , seq ) : NEW_LINE INDENT if ( pos == len ( S ) and ( len ( seq ) >= 3 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT num = 0 NEW_LINE for i in range ( pos , len ( S ) ) : NEW_LINE INDENT num = num * 10 + ( ord ( S [ i ] ) - ord ( '0' ) ) NEW_LINE if ( num > sys . maxsize ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( ord ( S [ pos ] ) == ord ( '0' ) and i > pos ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( len ( seq ) > 2 and ( num > ( seq [ - 1 ] + seq [ len ( seq ) - 2 ] ) ) ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( len ( seq ) < 2 or ( num == ( seq [ - 1 ] + seq [ len ( seq ) - 2 ] ) ) ) : NEW_LINE INDENT seq . append ( num ) NEW_LINE if ( splitIntoFibonacciHelper ( i + 1 , S , seq ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT seq . pop ( ) NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def splitIntoFibonacci ( S ) : NEW_LINE INDENT seq = [ ] NEW_LINE splitIntoFibonacciHelper ( 0 , S , seq ) NEW_LINE if ( len ( seq ) >= 3 ) : NEW_LINE INDENT for i in seq : NEW_LINE INDENT print ( i , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( - 1 , end = ' ' ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = "11235813" NEW_LINE splitIntoFibonacci ( S ) NEW_LINE DEDENT