{x}
blog image

Split Array into Fibonacci Sequence

You are given a string of digits num, such as "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:

  • 0 <= f[i] < 231, (that is, each integer fits in a 32-bit signed integer type),
  • f.length >= 3, and
  • f[i] + f[i + 1] == f[i + 2] for all 0 <= i < f.length - 2.

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 num, or return [] if it cannot be done.

 

Example 1:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

Example 2:

Input: num = "112358130"
Output: []
Explanation: The task is impossible.

Example 3:

Input: num = "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

 

Constraints:

  • 1 <= num.length <= 200
  • num contains only digits.

Solution Explanation for Split Array into Fibonacci Sequence

This problem asks us to split a string of digits into a Fibonacci-like sequence. A Fibonacci-like sequence is defined as a list of non-negative integers where each element (after the first two) is the sum of the previous two elements. The sequence must have at least three elements. Additionally, leading zeros are not allowed in the individual numbers (except for the number 0 itself).

The most efficient approach is using backtracking. We explore all possible ways to split the string into numbers, checking at each step if the current sequence is Fibonacci-like and within the 32-bit integer limit.

Algorithm

  1. Base Case: If the index i reaches the end of the string (i == n), and we have at least three numbers in our ans list, then we have found a valid Fibonacci-like sequence. Return true.

  2. Number Generation: We iterate through the string from index i to find potential numbers. We handle leading zeros by checking num[i] == '0'. If we encounter a leading zero, and the current number is not 0 itself, we break the inner loop because any further numbers starting with a leading zero are invalid.

  3. Bounds Check: We check if the current number x exceeds the maximum value of a 32-bit signed integer (231 - 1). If it does, we break the inner loop. We also check if the current number is greater than the sum of the last two numbers in our sequence. This is a crucial optimization; if it's bigger, there's no need to continue this branch of exploration.

  4. Fibonacci Check: If the current number x is the sum of the last two numbers in ans (or if ans has fewer than two elements), it's a valid Fibonacci-like addition. We append x to ans.

  5. Recursive Call: We recursively call dfs(j + 1) to explore the rest of the string. If the recursive call returns true, we have found a valid Fibonacci sequence, so we return true.

  6. Backtracking: If the recursive call returns false (meaning that this path doesn't lead to a valid Fibonacci sequence), we remove the last element from ans using ans.pop() (or its equivalent in other languages) and continue exploring other possibilities.

  7. Return Value: If the dfs function completes without finding a valid sequence, it returns false.

Time Complexity Analysis

The time complexity is exponential in the worst case, O(2n), where n is the length of the input string. This is because we potentially explore many different ways to split the string. However, the bound checks significantly prune the search space, preventing it from reaching the full exponential complexity in many scenarios. It's closer to O(n*m), where m is the average length of the numbers in the sequence, in most practical cases due to the numerous early exits and pruning of possibilities.

Space Complexity Analysis

The space complexity is dominated by the recursive call stack, which, in the worst case, could reach a depth of n. Therefore, the space complexity is O(n). The space used by the ans list is also O(n) in the worst case.

Code in Different Languages

The code provided in Python, Java, C++, and Go above implements this backtracking algorithm. They all share the same core logic, differing only in syntax and specific language features (e.g., data structure implementations). Each function performs the backtracking search described in the algorithm section above. Note that error handling (e.g., checking for integer overflow) is crucial for correctness.