/306. Additive Number
Previous|Next

306. Additive Number

Medium
Strings33.6% acceptance

Given a string of digits, determine if it can be split into at least three contiguous numbers such that, starting from the third number, each number is the sum of the previous two. Numbers must not have leading zeros unless the number is zero itself.

Example 1

Input: 1235813

Output: True

Explanation: Possible sequence: 1, 2, 3, 5, 8, 13. Each number is the sum of the previous two.

Example 2

Input: 1020305

Output: False

Explanation: No valid additive sequence can be formed due to leading zeros.

Example 3

Input: 000

Output: True

Explanation: Sequence: 0, 0, 0. Each number is the sum of the previous two.

Constraints

  • 2 <= len(digit_string) <= 35
  • digit_string consists only of digits (0-9)
  • Numbers in the sequence must not have leading zeros unless the number is zero
  • Sequence must contain at least three numbers
Python (current runtime)

Case 1

Input: '12122436'

Expected: True

Case 2

Input: '101202303'

Expected: False

Case 3

Input: '891720161'

Expected: True

Case 4

Input: '120122'

Expected: False

Case 5

Input: '0000'

Expected: True