## Sunday, October 30, 2016

### LeetCode 441 - Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:
n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.
https://discuss.leetcode.com/topic/65631/c-three-solutions-o-n-o-logn-o-1
The author means O(k), O(1), O(log(k)), where k is the number of staircases. In fact k is of order O(log(n)),

    int way1(int n) {
int level = 1;
for (long sum = 0; sum <= n; level++)
sum += level;
return max(level - 2, 0);
}

int way2(int n) {
return sqrt(2 * (long)n + 1 / 4.0) - 1 / 2.0;
}

int arrangeCoins(int n) {
long low = 1, high = n;
while (low < high) {
long mid = low + (high - low + 1) / 2;
if ((mid + 1) * mid / 2.0 <= n) low = mid;
else high = mid - 1;
}
return high;
}

x ^ 2 + x = 2 * n

x = sqrt(2 * n + 1/4) - 1/2
The problem is basically asking the maximum length of consecutive number that has the running sum lesser or equal to $n$. In other word, find $x$ that satisfy the following condition:
$1+2+3+4+5+6+7+...+x\le n$
$\sum _{i=1}^{x}i\le n$
Running sum can be simplified,
$\frac{x\cdot \left(x+1\right)}{2}\le n$
Using quadratic formula, $x$ is evaluated to be,
$x=\frac{1}{2}\cdot \left(-\sqrt{8\cdot n+1}-1\right)$ (Inapplicable) or $x=\frac{1}{2}\cdot \left(\sqrt{8\cdot n+1}-1\right)$
http://blog.csdn.net/mebiuw/article/details/52981579
public int arrangeCoins(int n) { /* 数学推导 (1+k)*k/2 = n k+k*k = 2*n k*k + k + 0.25 = 2*n + 0.25 (k + 0.5) ^ 2 = 2*n +0.25 k + 0.5 = sqrt(2*n + 0.25) k = sqrt(2*n + 0.25) - 0.5 */ return (int) (Math.sqrt(2*(long)n+0.25) - 0.5); }
https://discuss.leetcode.com/topic/65575/java-o-1-solution-math-problem
http://blog.csdn.net/cloudox_/article/details/53005388
The idea is about quadratic equation, the formula to get the sum of arithmetic progression is
sum = (x + 1) * x / 2
so for this problem, if we know the the sum, then we can know the x = (-1 + sqrt(8 * n + 1)) / 2
(1 + X) * X = 2n
4X * X + 4 * X = 8n
(2X + 1)(2X + 1) - 1 = 8n
X = (Math.sqrt(8 * n + 1) - 1)/ 2
If x is the answer, then n coins do fill x rows but don't fill x+1 rows. So we have x(x+1)/2 ≤ n < (x+1)((x+1)+1)/2. Which, using the other formula, turns into x ≤ (sqrt(8n+1) - 1) / 2 < x+1. So we indeed get the right answer by rounding down (sqrt(8n+1) - 1) / 2.
    public int arrangeCoins(int n) {
return (int)((-1 + Math.sqrt(1 + 8 * (long)n)) / 2);
}
https://discuss.leetcode.com/topic/65593/java-clean-code-with-explanations-and-running-time-2-solutions

X. Bisection
https://discuss.leetcode.com/topic/65593/java-clean-code-with-explanations-and-running-time-2-solutions
Time Complexity:
• Best Case O(log_b(n)) : With respect to the input, the algorithm will always depend on the value of input.
• Average Case O(log_b(n)) : With respect to the input, the algorithm will always depend on the value of input.
• Worst Case O(log_b(n)) : With respect to the input, the algorithm will always depend on the value of input.
Auxiliary Space:
• Worst Case O(1) : Additional variables are of constant size.

#### Algorithm

Approach: Binary Search
The problem is basically asking the maximum length of consecutive number that has the running sum lesser or equal to n. In other word, find x that satisfy the following condition:
1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + x <= n
sum_{i=1}^x i <= n
Running sum can be simplified,
(x * ( x + 1)) / 2 <= n
Binary search is used in this case to slowly narrow down the x that will satisfy the equation. Note that 0.5 * mid * mid + 0.5 * mid does not have overflow issue as the intermediate result is implicitly autoboxed to double data type.
https://ratchapong.com/algorithm-practice/leetcode/arranging-coins
The problem is basically asking the maximum length of consecutive number that has the running sum lesser or equal to $n$. In other word, find $x$ that satisfy the following condition:
$1+2+3+4+5+6+7+...+x\le n$
$\sum _{i=1}^{x}i\le n$
Running sum can be simplified,
$\frac{x\cdot \left(x+1\right)}{2}\le n$
Binary search is used in this case to slowly narrow down the $x$ that will satisfy the equation. Note that 0.5 * mid * mid + 0.5 * mid does not have overflow issue as the intermediate result is implicitly autoboxed to double data type.

    public int arrangeCoins(int n) {
int start = 0;
int end = n;
int mid = 0;
while (start <= end) {
mid = (start + end) >>> 1;
if ((0.5 * mid * mid + 0.5 * mid) <= n) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start - 1;
}

O(k)
http://www.cnblogs.com/grandyang/p/6026066.html

    int arrangeCoins(int n) {
int cur = 1, rem = n - 1;
while (rem >= cur + 1) {
++cur;
rem -= cur;
}
return n == 0 ? 0 : cur;
}