Split Array into Fibonacci Sequence

Medium

Google

2 views

Topics:

StringsRecursionArrays

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, (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.

Write a function that will 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.

What is the time and space complexity of your solution?

Split Array into Fibonacci Sequence

Medium

Google

2 views

Topics:

StringsRecursionArrays

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, (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.

Write a function that will 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.

What is the time and space complexity of your solution?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the input string cannot be split into a Fibonacci sequence? Should I return an empty list or null?
Are leading zeros allowed in the individual numbers of the Fibonacci sequence?
What is the maximum length of the input string `S`?
Are there any constraints on the range of values that the numbers in the Fibonacci sequence can take?
If multiple Fibonacci sequences are possible, should I return any one of them or is there a specific criterion for choosing one?

Brute Force Solution

Approach

The brute force approach to splitting a sequence into a Fibonacci sequence involves trying every single way to divide the numbers. We explore all combinations to see if any of them form a valid Fibonacci sequence.

Here's how the algorithm would work step-by-step:

Start by trying to split the input sequence at the very beginning, taking just the first one or more digits as the first number of a potential Fibonacci sequence.
Then, try splitting the remainder of the sequence to get the second number in the sequence.
From there, calculate what the next Fibonacci number should be by adding the first two.
Check if the remaining sequence starts with that calculated number. If it does, then we're still on the right track.
Keep repeating the process of calculating the next Fibonacci number and checking if it matches the remaining part of the input sequence.
If at any point the next Fibonacci number doesn't match the remaining sequence, go back and try a different initial split.
If the entire sequence gets used up while successfully forming a Fibonacci sequence, then that's a solution. If not, keep trying other splits.
Repeat this exhaustive process until we have explored all possible ways of splitting the original sequence.

Code Implementation

def split_into_fibonacci_brute_force(input_string):
    length_of_input = len(input_string)
    result = []

    def backtrack(current_index, sequence):
        if current_index == length_of_input and len(sequence) >= 3:
            result.append(sequence)
            return True

        for j in range(current_index + 1, length_of_input + 1):
            number_string = input_string[current_index:j]

            # Prevent leading zeros
            if number_string.startswith('0') and len(number_string) > 1:
                continue

            current_number = int(number_string)

            # Check for integer overflow
            if current_number > 2**31 - 1:
                continue

            if len(sequence) < 2:
                if backtrack(j, sequence + [current_number]):
                    return True
            else:
                # Validate the fibonacci condition
                if sequence[-1] + sequence[-2] == current_number:
                    if backtrack(j, sequence + [current_number]):
                        return True
        return False

    backtrack(0, [])
    if result:
        return result[0]
    else:
        return []

Big(O) Analysis

Time Complexity

O(C^n) – The algorithm explores all possible splits of the input string of length n to find a Fibonacci sequence. In the worst case, it might need to examine an exponential number of combinations, where each position in the string could potentially mark a split between two numbers. Specifically, for each index, we're deciding whether to split or not, which gives us 2 options at each index leading to a runtime of O(2^n). However, we're dealing with possibly large numbers which will factor into an exponential runtime which can be loosely represented as O(C^n) for some constant C.

Space Complexity

O(N) – The brute force approach, as described, implicitly uses recursion to explore different splits. In the worst case, where a valid Fibonacci sequence is not found until the very end, the recursion depth could reach N, where N is the number of digits in the input string. Each recursive call adds a new frame to the call stack, which stores function arguments and local variables. Therefore, the auxiliary space complexity is proportional to the maximum recursion depth, which is O(N).

Optimal Solution

Approach

The challenge is to break a string of digits into a Fibonacci sequence. The best way to do this is to try building the sequence one number at a time, making sure each new number follows the Fibonacci rule (it equals the sum of the previous two). If it doesn't, we backtrack and try a different starting point or number length.

Here's how the algorithm would work step-by-step:

Start by trying to figure out what the first two numbers of the potential Fibonacci sequence could be.
Once you have the first two numbers, check if their sum exists as the next number in the string.
If the sum exists, add it to your sequence and continue. This means the new 'first number' is the old 'second number', and the new 'second number' is the sum you just found.
Keep building the sequence this way. Each new number must be the sum of the previous two.
If at any point the sum doesn't exist in the string, or the numbers get too big (more than 32 bits), go back and try different values for the initial two numbers.
If you reach the end of the string and you have at least three numbers that form a valid Fibonacci sequence, you've found a solution!
If you've exhausted all possibilities for the initial two numbers without finding a valid sequence, then the string cannot be split into a Fibonacci sequence.

Code Implementation

def split_into_fibonacci(digit_string):
    sequence_list = []
    string_length = len(digit_string)

    def backtrack(index_position):
        if index_position == string_length and len(sequence_list) >= 3:
            return True

        for j in range(index_position + 1, string_length + 1):
            substring = digit_string[index_position:j]
            
            # Leading zero check.
            if len(substring) > 1 and substring[0] == '0':
                continue

            try:
                number = int(substring)
            except ValueError:
                continue

            # Number should be within 32 bit range.
            if number >= (1 << 31):
                continue

            if len(sequence_list) < 2 or number == sequence_list[-1] + sequence_list[-2]:
                sequence_list.append(number)

                # Recursively check if we can extend the sequence
                if backtrack(j):
                    return True

                sequence_list.pop()
        return False

    # Iterate to find possible values for first two numbers
    for i in range(1, string_length // 2 + 1):
        
        #Try different starting points.
        sequence_list = []
        if backtrack(0):
            return sequence_list

    return []

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input string of length n to determine the first two numbers of the potential Fibonacci sequence. This involves nested loops, each potentially iterating up to n times to explore different lengths for the initial two numbers. For each pair of initial numbers, the algorithm attempts to extend the Fibonacci sequence, but this extension process is bounded by the length of the original string n. Therefore, the dominant factor in the time complexity is the nested iteration over potential starting pairs, leading to approximately n * n operations. This simplifies to a time complexity of O(n²).

Space Complexity

O(N) – The primary space usage comes from the list that stores the Fibonacci sequence found, where N represents the length of the input string. In the worst case, the entire string could be parsed into a Fibonacci sequence of numbers with each digit represented. The recursion stack depth can also go up to N in the worst-case scenario where we explore almost all possible prefixes before finding the valid fibonacci sequence. Therefore, the space complexity is dominated by the size of the fibonacci sequence list and recursion depth, both of which are proportional to the input string length N.

Edge Cases

Case	How to Handle
Empty or null input string	Return an empty list if the input string is null or empty as a Fibonacci sequence requires at least three numbers.
Input string too short (length < 3)	Return an empty list as a valid Fibonacci sequence needs at least three numbers derived from the string.
Input string starts with leading zeros which may cause incorrect integer conversion.	Handle leading zeros by ensuring that any number with leading zeros is equal to 0, or if greater than one digit, is not a valid option.
Integer overflow during number parsing from the string	Check if the parsed integer exceeds the maximum value of a 32-bit signed integer after parsing, and return an empty list in that case.
No valid Fibonacci sequence exists within the string	Return an empty list if the backtracking search completes without finding a valid Fibonacci sequence of at least three numbers.
Multiple valid Fibonacci sequences exist; solution needs to return only one	The backtracking search finds the first valid sequence and short-circuits; subsequent possible valid sequences are not considered.
String contains only zeros	Handle the special case of all zeros correctly forming a valid Fibonacci sequence of zeros.
Very long input string may lead to stack overflow due to deep recursion	The problem can be structured so that the recursion depth is limited; early termination can avoid deep stack depth.