Last Updated: 12 Apr, 2021
Split Array Into Fibonacci Sequence
Moderate
Asked in companies
In this problem, You are given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579]. Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:
1: 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
2: F.length >= 3;
3: and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.
Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.
Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.
Example :
Input: "123456579"
Output: [123, 456, 579]
Explanation:
Since 123 + 456 = 579, therefore the given string can be broken into fibonacci sequence
Input Format
The first line of input contains a single integer ‘T’ denoting the number of test cases given.
The first line of each test case input contains a string that is required to be broken into different Fibonacci sequences.
Output Format:
For every test case, Return the first Fibonacci-like sequence list (array) which can be formed by splitting from S, or return [] if it cannot be done.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraint :
1 <= T <= 100
1 <= S.length <= 200
Time Limit: 1 sec
Approaches
Using the above intuition, we can formalize the following concept that, the first two elements which our resultant Fibonacci sequence list (array) will contain, uniquely helps us determine and figure out the rest of the sequence.
For each of the first two elements, assuming they have no leading zero, let's iterate through the rest of the string. At each stage, we expect a number less than or equal to 2^31 - 1 that starts with the sum of the two previous numbers.
The algorithm to calculate the required smallest difference will be:-
- Start by iterating over the given digits present in the string and keep assigning the first number ‘a’ of some particular length up to the total length of the string ‘S’.
- Break the iteration if the number is non-zero but has leading zeros in it.
- Similarly, also initialize a second number ‘b’ of length up to the total length of the string ‘S’ and break the iteration if the number is non-zero but has leading zeros.
- Keep traversing the remaining elements (digits) present in the string ‘S’, initialize a list (array) ‘fib’ comprising of the two numbers as the first and second number in the sequence, and check for ‘k’ starting from the index+1 from our second digit index in the string ‘S’ up to the length of the string ‘S’.
- Keep calculating the next Fibonacci number in the sequence using the previous two numbers that we initialized (‘a’ and ‘b’).
- I.e. nxt = fib[-1] + fib[-2] ( or nxt = a + b )
- b. Now check if the next number generated is present in the remaining start of the string ‘S’.
- Update the length of the Fibonacci number ‘k’ with the length of our next generated number ‘nxt’ and add the number in our ‘fib’ list (array).
- Else break out of the iteration.
- Once we have iterated for all the remaining elements present in the string ‘S’, we check if the length of our list (array) ‘fib’ obtained is greater than or equal to 3 or not. We return the list (array) if such a sequence is possible. Otherwise, we return an empty list.