441.Arranging Coins

Posted on | In

Solution 1: accepted 64ms 10%

1
2
3
4
5
6
7
8
9
10
public int arrangeCoins(int n) {
    int row = 0;
    int cost = 1;
    while (n >= cost) {
        n -= cost;
        row++;
        cost++;
    }
    return row;
}

Solution 2: accepted 46ms 69%

Cost of coins: 1+2+3+…+k = k(1+k)/2
Calculate the maximum of k where k(1+k) <= 2n
(0 <= k < n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int arrangeCoins(int n) {
    long lo = 0;
    long hi = n;
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2; // why + 1? prevent the infinite loop for lo
        if (mid * (mid + 1) < (long)2 * n) {
            lo = mid;
        } else if (mid * (mid + 1) > (long)2 * n) {
            hi = mid - 1;  // since lo is inclusive, hi can be exclusive
        } else {
            return (int)mid;
        }
    }
    return (int)lo;
}

Alternative from this post

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int arrangeCoins(int n) {   
    //convert int to long to prevent integer overflow
    long nLong = (long)n;
    long st = 0;
    long ed = nLong;
    long mid = 0;
    while (st <= ed){
        mid = st + (ed - st) / 2;
        if (mid * (mid + 1) <= 2 * nLong){
            st = mid + 1;
        }else{
            ed = mid - 1;
        }
    } 
    return (int)(st - 1);
}

Solution 3

We have many math solutions.