Google – Power Sum
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)
Read full article from Google – Power Sum
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;}