Medium

Quiz

#306 Additive Number

APPROACH

A string of digits forms an additive sequence if its characters can be split into at least three numbers where every number from the third onward equals the sum of the two preceding it.

Given a digit-only string, return true if it is an additive number or false otherwise.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"

Output: true

Explanation:

The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"

Output: true

Explanation:

The additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

1 of 4

1:00

What is the optimal approach for this problem?