Split Array Into Fibonacci Sequence
01 · Problem
You are given a string num made of digits. Cut it into consecutive pieces, read each piece as a non-negative integer, and check whether the resulting list f is Fibonacci-like:
fhas at least 3 numbers.f[i] + f[i+1] == f[i+2]for every validi.- Every number fits in a signed 32-bit integer, i.e.
0 <= f[i] <= 2^31 - 1. - No piece has a leading zero, except the piece
"0"itself.
All digits of num must be used, in order.
Several splits may work, so the answer is fixed by search order: try lengths for the first number from shortest to longest, and for each, try lengths for the second number from shortest to longest. Once the first two numbers are chosen, the rest of the sequence is forced. Return the first sequence found in this order as an array of integers, or an empty array [] if no split works.
02 · Examples
num = "1101111"
[11,0,11,11]
Starting with 1 leads nowhere. Starting with 11, the second number 0 gives 11 + 0 = 11, then 0 + 11 = 11, consuming the whole string.
num = "112358130"
[]
The prefix splits as 1,1,2,3,5,8,13 but the trailing "0" breaks the pattern, and no other choice of the first two numbers works.
num = "123456579"
[123,456,579]
123 + 456 = 579, which uses every digit. No shorter choice for the first two numbers succeeds.
03 · Constraints
- 01`1 <= num.length <= 200`
- 02`num` contains only digits `0`-`9`
- 03Every number in the returned sequence must satisfy `0 <= x <= 231 - 1`
- 04Return `[]` if no valid split exists
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.