algoadvance

Leetcode 842. Split Array into Fibonacci Sequence

Problem Statement

Given a string S of digits, let us split the string into a Fibonacci-like sequence such that:

1. Each digit in the string belongs to one of the integers in the sequence.
2. Each integer must not contain leading zeros, except for the integer 0 itself.
3. The sequence should contain at least three integers.
4. The sequence should adhere to the Fibonacci property such that the sum of the first two integers equals the third integer (and this property holds for all consecutive triplets in the sequence).

Return the sequence or an empty array if it is impossible to form such a sequence.

Clarifying Questions

1. Input Constraints: What are the constraints on the length of the string S?
   • Answer: The length of S is at most 200 characters.
2. Output Detail: If multiple sequences are possible, is there any preference?
   • Answer: Any valid sequence can be returned; there’s no preference specified.
3. Data Type: Should we consider large Fibonacci numbers potentially leading to integer overflows?
   • Answer: Yes, the Fibonacci numbers if generated from very long strings can be very large. We will manage this scenario using long data types.

Strategy

We will use a backtracking approach to explore all possible ways to split the string into a valid Fibonacci sequence. Our constraints will ensure that:

• Each number must not have a leading zero (except the single digit ‘0’).
• The sum of two consecutive numbers should match the next number in the sequence.
• We stop and backtrack if any of these conditions fail.

Algorithm Steps:

1. Try every possible first number by iterating over possible lengths.
2. Try every possible second number starting from the end of the first number.
3. Validate if the sequence can grow following the Fibonacci rules.
4. If a valid sequence of at least three numbers is found, return it.
5. If no valid sequence is found after all possibilities, return an empty array.

Code

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    std::vector<int> splitIntoFibonacci(std::string S) {
        std::vector<int> result;
        backtrack(S, result, 0);
        return result;
    }

private:
    bool backtrack(const std::string& S, std::vector<int>& result, size_t start) {
        if (start == S.size() && result.size() >= 3) {
            return true;
        }
        
        long long num = 0;
        for (size_t i = start; i < S.size(); ++i) {
            // Prevent numbers with leading zeros (except '0')
            if (i > start && S[start] == '0') break;
            
            num = num * 10 + (S[i] - '0');
            // If the number exceeds the int limit, break
            if (num > INT_MAX) break;
            
            if (result.size() >= 2) {
                long long sum = static_cast<long long>(result[result.size() - 1]) + result[result.size() - 2];
                if (num < sum) continue;
                if (num > sum) break;
            }
            
            result.push_back(static_cast<int>(num));
            if (backtrack(S, result, i + 1)) {
                return true;
            }
            result.pop_back();
        }
        
        return false;
    }
};

Time Complexity

• The worst-case time complexity is difficult to state precisely but can be approximated.
• The outer loops iterate over up to O(N) digits in S.
• For each start index, the nested loops break down possible splits, which would exponentially explode. Thus, though the worst-case can seem like O(2^N) due to the combinatorial nature of splitting, the string length constraint (max 200) ensures practical computability.

We optimize by breaking early on invalid conditions (leading zeroes, oversize numbers). This practical optimization bounds runtime effectively for given constraint lengths.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?