Split Array Into Fibonacci Sequence

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in companies
AdobeKempstonTCS

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
1101111
112358130
0123
Sample Output 1:
YES
NO
NO
Explanation For Sample Input 1:
For the first test case, The output [11, 0, 11, 11] is the required Fibonacci sequence here. So since there is one such sequence available, therefore, the output is “YES” here.


For the second test case, The task of splitting the string into a Fibonacci sequence is not Possible. Therefore you output an empty list (array). The result here would be “NO”.


For the third test case, Since there are  Leading zeroes, which are not allowed, so "01", "2", "3" is not a valid Fibonacci sequence. Hence the result “NO”.
Sample Input 2:
2
123456579
11235813
Sample output 2:
YES
YES
Hint

Try to notice the fact that the first two elements of the array can be uniquely used to determine the rest of the sequence.

Approaches (1)
Split Array into Fibonacci Sequence

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.
Time Complexity

O(N * N), where ‘N’ is the length of the ‘S’.

 

Since we are iterating over all the elements given in the string ‘S’ which is an O(N) operation and doing so in a nested fashion to find the first two Fibonacci numbers in the sequence which could uniquely deter

Space Complexity

O(N), where ‘N’ is the length of the ‘S’.

 

Since, Here, we use a list (array) to store the required Fibonacci sequence, therefore, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Split Array Into Fibonacci Sequence
Full screen
Console