## Monday, August 8, 2016

Given an integer n, return sum of n^0 + n^1 + … + n^n.
[Solution]
1. Brute Force is straightforward. O(n) time
2. Binary Search, O(logn) time
In both solution, be careful of the Overflow!
[Prove]
sum = n^0 + n^1 + … + n^n
= n^0 + n^1 + … + n^(n/2) + n^(n/2 + 1) + n^(n/2 + 2) + … + n^n
= n^0 + (n^1 + … + n^n/2) + (n^1 + … + n^n/2) * n^(n/2)
= n^0 + half + half * n^(n/2)
`public` `int` `sum(``int` `n) {`
`  ``if` `(n == ``0``) {`
`    ``return` `0``;`
`  ``}`

`  ``int` `result = sum(n, n);`
`  ``return` `result == -``1``? -``1` `: result + ``1``;`
`}`

`private` `int` `sum(``int` `n, ``int` `p) {`
`  ``if` `(p == ``0``) {`
`    ``return` `1``;`
`  ``}`
`  ``if` `(p == ``1``) {`
`    ``return` `n;`
`  ``}`

`  ``int` `half = sum(n, p / ``2``);`
`  ``long` `result = (``long``) (half + half * Math.pow(n, p / ``2``));`
`  ``if` `(p % ``2` `!= ``0``) {`
`    ``result += Math.pow(n, p);`
`  ``}`

`  ``if` `(result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {`
`    ``return` `-``1``;`
`  ``}`

`  ``return` `(``int``) result;`
`}`