Daily Archives: January 7, 2016

Additive Number

https://leetcode.com/problems/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, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Solution
This is a permutation a like problem. The key to solve it is to build the first number and second number. Then we check if string is an additive number started by the 2 number. Let len1 is the length of number1, len2 for number2, n for length of string. So, the length of the next number should be greater than or equal to max(len1, len2). So we have condition that n – len1 + len2 >= max(len1, len2)

Then we should write¬†isValid(String str, int i, int j) function to check if str is a additive number with first number¬†[0,…,i], second number is [i+1,…,j]. When writing this function, we should eliminate exception number like ‘012’, ’01’. On the other hand, we should pay attention that ‘0’ is a valid number.

check my code on github: link

pascal triangle

https://leetcode.com/problems/pascals-triangle-ii/

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Analysis
Matrix like below is a pascal triangle p[][]. For row i, column j, p[i][j] it has value C(i, j) [Binomial Coefficient].

pascaltriangle

Below is the formula which can help us get C(n, m) from C(n, m – 1).

pascaltriangle2

In this way, we can get elements in row i in O(n) time.

check my code on github: link