LietCode
Split Array into Fibonacci Sequence

Split Array into Fibonacci Sequence

Abhi's photo
Abhi
·

3 min read

Explain the Problem

Given a string of digits, return all possible ways to split it into a Fibonacci-like sequence, where a sequence of integers is Fibonacci-like if:

  1. The sequence starts with [F1, F2] where F1 and F2 are both non-negative integers.

  2. For all i >= 2, Fi = Fi-1 + Fi-2.

Return any valid Fibonacci-like sequence, or return an empty array if no sequence exists.

Example:

Input: s = "123456579"

Output:

[123, 456, 579]

Solution:

  1. Allow time to think and solve.

Take a moment to think about how you would solve this problem using backtracking.

Once you feel ready, let me know, and we can proceed to the next step.

1) Explain the problem

The problem is to split a given string of digits into a Fibonacci sequence. A Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. In this problem, the sequence should start with any two numbers, and the numbers should be formed by splitting the given string without reordering the digits.

2) Short easy to remember solution/approach

  1. Try all possible splits for the first two numbers.

  2. Use backtracking to check if the rest of the string can form a valid Fibonacci sequence.

3) Solution in JavaScript with code commenting

function splitIntoFibonacci(S) {
    const result = [];

    function backtrack(index) {
        if (index === S.length && result.length >= 3) {
            return true;
        }

        let num = 0;
        for (let i = index; i < S.length; i++) {
            if (i > index && S[index] === '0') break; // Avoid numbers with leading zeros
            num = num * 10 + (S[i] - '0');
            if (num > Math.pow(2, 31) - 1) break; // Avoid overflow

            const size = result.length;
            if (size >= 2 && num > result[size - 1] + result[size - 2]) break; // Ensure valid Fibonacci sequence
            if (size <= 1 || num === result[size - 1] + result[size - 2]) {
                result.push(num);
                if (backtrack(i + 1)) return true;
                result.pop();
            }
        }

        return false;
    }

    if (backtrack(0)) return result;
    return [];
}

// Example usage:
const S = "123456579";
console.log(splitIntoFibonacci(S)); // Output: [123, 456, 579]

4) Explanation the solution in an easy-to-understand way with real-life example

Imagine you have a long string of numbers like "123456579". You want to find a way to split this string into parts that form a Fibonacci sequence. A Fibonacci sequence is like a growing family where each new member is the sum of the last two members.

For example, if the family starts with "123" and "456", the next family member should be "579" because 123 + 456 = 579. So, our job is to figure out if we can split the string into such a growing family.

5) Code explanation in pointers

  • Initialize result: We have an empty array to store our sequence.

  • Backtracking function: This function will try to create the sequence.

  • Loop through string: Start from the current index and try all possible numbers.

  • Avoid leading zeros: Skip numbers that start with '0' unless it's just '0'.

  • Check for overflow: Ensure the number doesn’t exceed the 32-bit integer limit.

  • Check Fibonacci property: If we have at least two numbers, ensure the current number is the sum of the last two.

  • Recursive call: If the current number fits, add it to the sequence and continue. If it doesn't work out, remove it and try the next possibility.

  • Return result: If we find a valid sequence, return it; otherwise, return an empty array.

6) Complexities

  • Time complexity: (O(2^n)) where (n) is the length of the string. This is because we are trying every possible split combination using backtracking.

  • Space complexity: (O(n)) for the recursion stack and the result array.

backtracking