Additive Number 🌟

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358" is an additive number because 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

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

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

Solution 1: (not completed)

Runtime Error Message:Line 8: java.lang.NumberFormatException: For input string: “”


public class Solution {
    public boolean <gs id="dcfddffd-9704-4bd0-883c-adff200cf315" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">isAdditiveNumber(String</gs> <gs id="876fa84c-c07a-4518-b4ac-3d305ec8d33d" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num)</gs> {
        for (int i = 1; i &lt; <gs id="0f995a0d-cf5a-4163-8aab-365cf7da7a42" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num.length();</gs> i++) {
            for (int j = i + 1; j &lt; <gs id="76d9b8ea-cd2d-40cb-867a-d5f313429b1f" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num.length();</gs> j++) {                 String s1 = <gs id="b1fc9aa1-80ed-42db-9566-c677ac4af6d9" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num.substring</gs> (0,i);                 String s2 = <gs id="35a87ed8-841b-4ee0-b672-35a32d3901b9" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num.substring</gs> (i, j-i);                 Long d1 = Long.parseLong(s1);                 Long d2 = Long.parseLong(s2);                                  //check if the first digit is 0                  if ((s1.charAt(0) == '0' &amp;&amp; s1.length() &gt; 1)
                || (s2.charAt(0) == '0' &amp;&amp; s2.length() &gt; 1))
                    continue;
                Long next = d1 + d2;
                String <gs id="c3c25fac-a89f-4ceb-b9ea-faf5a1e2de72" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">nexts</gs> = String.valueOf(next);
                String now = s1 + s2 + <gs id="22fe3554-2ab0-4f93-a5ae-7dacfd1e2a8d" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">nexts;</gs>
                while (now.length () &lt; <gs id="5abb38e7-ac6a-49a8-93ba-c2431ce9df06" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num.length())</gs> {
                    d1 = d2;
                    d2 = next;
                    next = d1 + d2;
                    <gs id="12cca24a-68a0-4539-89f4-67c8dbd8e811" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">nexts</gs> = String.valueOf(next);
                    now += <gs id="09b49823-cbd0-4531-b691-c1fe6f7e1563" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">nexts;</gs>
                }
                if (now == <gs id="f36888af-c064-4547-90e9-06eb724c0628" ginger_software_uiphraseguid="a417abaf-7b63-4c65-b453-b6becd5641bc" class="GINGER_SOFTWARE_mark">num)</gs> return true;
            }
        }
        return false;
    }
}

 

Other solutions: Leetcode discussion

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s