【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.
問題解
この問題はプッシュで始まりましたが、butはタイムアウトしました.後で考えてみると、数学の方法が発見された:m階に必要なcoinsはm(m+1)/2である.既存のm個の硬貨は,x:x(x+1)/2=nと仮定できる.一元二次方程式を解き、正根を整頓し、得られるstair numberを得る.ここでは、なぜ下に整えればいいのか理解していない人が多い.実際には、正のルートx 1が下にkに整列されていると仮定すると、kがx 1以下でk+1未満であることを満たすことができる.(小さい番号を打つことができなくて、酔っています)それではcoinsがk*(k+1)/2の時のstairの数はkで、coinsが(k+1)(k+2)/2の時、stairの数はk+1です;従って、stair number=kは、k*(k+1)/2および(k+1)(k+2)/2のすべてのn値に対して、では、このときのk値は達成可能なstair numberである.

class Solution {
public:
    int arrangeCoins(int n) {
       return sqrt(2 * (long)n + 1 / 4.0) - 1 / 2.0;
    }
};

この問題をやり終えたら、中学校に帰って再び本を読むことができることに気づいた(表情が出ない).