ArrangingCoins [source code]

public class ArrangingCoins {
static
/******************************************************************************/
public class Solution {
    public int arrangeCoins(int n) {
        long sum = 0;
        int i = 1;
        while (sum <= n) {
            sum += i++;
        }
        return i - 2;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ArrangingCoins.Solution tester = new ArrangingCoins.Solution();
        int[] inputs = {4, 5, 8, 1804289383, 2147483647, 846930886};
        for (int i : inputs) System.out.println(i + " -> " + tester.arrangeCoins(i));
        // System.out.println(tester.arrangeCoins(846930886));
    }
}

也是好久没有见过这么恶心的题目了; 刚开始这个题目是很简单的思路, 就是直接用求和公式来做, 最后的结果肯定是在平方根的周围浮动:

public class Solution {  
    public int arrangeCoins(int n) {  
        int root = (int) Math.sqrt(2 * n);  
        if ((long) (root * (root + 1)) <= 2 * n) return root;  
        else return root - 1;  
    }  
}

但是立刻这个 code 就被 break 了, 就是用 overflow:

java> long n1 = 60070 * 60071  
long n1 = -686502326  
java> Math.sqrt(2 * 1804289383)  
java.lang.Double res6 = NaN

乘法和平方根都用不起来了;

最后只能用穷举, 也就是求和的思路来做; 就是这样, 还是有一个 overflow 的case; 原因是 sum 这个累加和, 要用 long 来避免overflow;

最后的速度是54ms (42%), 这个题目反正是没什么好说的了;

这个是 submission 上面的一个最优解:

public class Solution {  
    public int arrangeCoins(int n) {          
        return (int) (Math.sqrt(8.0*n+1)-1)/2;  
    }  
}

这个其实速度也没比我的快多少: 52(49); 不过代码很简洁; 这个方法我主要是没有想到, 实际上也没有复杂多少, 就是把那个二次方程的解直接解出来了;

这个是 discussion 上面看到的另外一个方法, 这个方法比我的方法更加先进一点:

public class Solution {  
    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;  
    }  
}

讲实话 Binary Search 实际上我也是想到了的, 不过没有想去做, 这题最好还是能够想到这个方法; 从头开始搜是在是太蠢了;
同样的, 一个问题前面已经强调过好几次了, 就是注意 Binary Search 的标准写法, 另外, 这里他的 if 的 header 里面用的是左边乘0.5而不是右边乘2, 这个一定程度上也是为了避免 overflow;

事实上, 这个是作者的说法:
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.

也就是说, 这里他还故意用了 double 来做一个防止 overflow 的处理;

Problem Description

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.

Difficulty:Easy
Total Accepted:28.1K
Total Submissions:77.6K
Contributor: LeetCode
Companies
godaddy
Related Topics
binary search math