Approach #1: Brute Force [Accepted]

Intuition

The first two elements of the array uniquely determine the rest of the sequence.

Algorithm

For each of the first two elements, assuming they have no leading zero, let's iterate through the rest of the string. At each stage, we expect a number less than or equal to 2^31 - 1 that starts with the sum of the two previous numbers.

Complexity Analysis

  • Time Complexity: , where is the length of S, and with the requirement that the values of the answer are in length.

  • Space Complexity: .


Analysis written by: @awice.