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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Split Array into Fibonacci Sequence

Difficulty: Medium

Problem Description

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] < 2^31
  • f.length >= 3
  • 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.

Key Insights

  • We need to find a way to partition the given string into valid parts that can form a Fibonacci sequence.
  • Each number in the sequence must be a valid integer (i.e., no leading zeros unless it's 0).
  • The Fibonacci condition must hold: the sum of the two preceding numbers should equal the next number.
  • The search space is limited given the constraints, but may require backtracking to explore different partitions.

Space and Time Complexity

Time Complexity: O(n^3) - where n is the length of the string, due to the nested loops for exploring different splits. Space Complexity: O(n) - for storing the sequence of valid integers during backtracking.

Solution

To solve this problem, we will use a backtracking approach to explore different ways of splitting the string into valid integers. We will keep track of the last two numbers in the Fibonacci sequence and check if their sum equals the next number. We will also ensure that no number has leading zeros, except for zero itself.

  1. Use a recursive function to try different splits of the string.
  2. For each split, convert the substring to an integer and check the leading zero condition.
  3. If we have at least three numbers and they satisfy the Fibonacci condition, return the sequence.
  4. If no valid sequence is found, return an empty list.

Code Solutions

def splitIntoFibonacci(num: str):
    def backtrack(start, seq):
        if start == len(num) and len(seq) >= 3:
            return seq
        for i in range(start + 1, len(num) + 1):
            part = num[start:i]
            if (len(part) > 1 and part[0] == '0') or int(part) >= 2**31:
                break
            seq_len = len(seq)
            if seq_len >= 2 and int(part) != seq[seq_len - 1] + seq[seq_len - 2]:
                continue
            seq.append(int(part))
            result = backtrack(i, seq)
            if result:
                return result
            seq.pop()
        return []
    
    return backtrack(0, [])
← Back to All Questions