We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Array into Fibonacci Sequence

Number: 872

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a string of digits, determine if you can split it into a Fibonacci-like sequence where each number (stored as a 32-bit signed integer) is the sum of the two preceding ones. The sequence must contain at least three numbers, and no number in the sequence should have extra leading zeroes (except for the number 0 itself). Return any valid Fibonacci-like sequence, or an empty list if no such sequence exists.

Key Insights

  • Use backtracking to explore all possible partitions of the string.
  • Ensure that each number is less than 2^31 to fit within a 32-bit integer.
  • Avoid partitions that lead to numbers with leading zeros.
  • When there are at least two numbers, the next number must equal the sum of the previous two; otherwise, prune the recursion early.
  • The worst-case time complexity is high, but early pruning helps with average cases.

Space and Time Complexity

Time Complexity: O(2^n) in the worst-case scenario due to backtracking. Space Complexity: O(n) for recursion depth and storing the current Fibonacci sequence.

Solution

We approach the problem using a backtracking algorithm. First, we iterate through the string to choose the first two numbers. Then, we recursively check if the remainder of the string can form a valid Fibonacci sequence using these initial numbers. At each step, we validate the following:

  1. The current segment does not start with a leading zero unless it is "0".
  2. The current number does not exceed the bounds of a 32-bit signed integer.
  3. If the sequence has at least two numbers, the next number must equal the sum of the last two. If the current segment is greater than this expected sum, we can prune the recursion early. The algorithm uses an array (or list) to store the current sequence and recurses until either a valid sequence is obtained or all possibilities are exhausted.

Code Solutions

# Python solution for Split Array into Fibonacci Sequence

class Solution:
    def splitIntoFibonacci(self, num: str):
        # Helper function for backtracking
        def backtrack(index, path):
            # If we have reached the end of the string and have a valid sequence, return True.
            if index == len(num) and len(path) >= 3:
                return True
            # Try all possible partitions starting at index.
            for i in range(index, len(num)):
                # Prevent numbers with extra leading zeros.
                if num[index] == "0" and i > index:
                    break
                current_str = num[index:i+1]
                current_number = int(current_str)
                # Ensure the number is within 32-bit signed integer limit.
                if current_number > 2**31 - 1:
                    break
                # When we have at least two numbers, enforce the Fibonacci property.
                if len(path) >= 2 and current_number != path[-1] + path[-2]:
                    if current_number > path[-1] + path[-2]:
                        break
                    continue
                # Include the number in the current path.
                path.append(current_number)
                if backtrack(i+1, path):
                    return True
                # Backtrack if adding current number doesn't lead to a solution.
                path.pop()
            return False

        result = []
        backtrack(0, result)
        return result

# End of Python solution
← Back to All Questions