GitHub Viewer
// Source : https://leetcode.com/problems/arranging-coins/
// Id : 441
// Author : Fanlu Hai
// Date : 2018-04-17
public class ArrangingCoins {
public int arrangeCoinsWithLong(int n) {
int rows = 0;
long coins = 0;
while (true) {
// System.out.println(n + "**" + coins + " " + rows);
if (n > coins) {
rows++;
coins += rows;
} else if (n == coins) {
return rows;
} else {
return rows - 1;
}
}
}
//faster than 82.04%, smaller than 100%
public int arrangeCoins(int n) {
int rows = 0;
long coins = 0;
while (true) {
// System.out.println(n + "**" + coins + " " + rows);
if (n > 0) {
rows++;
// use n - row instead of coins + to avoid int overflow
n -= rows;
} else if (n == 0) {
return rows;
} else {
return rows - 1;
}
}
}
public static void main(String[] args) {
ArrangingCoins arrangingCoins = new ArrangingCoins();
System.out.println(arrangingCoins.arrangeCoins(0));
System.out.println(arrangingCoins.arrangeCoins(1));
System.out.println(arrangingCoins.arrangeCoins(5));
System.out.println(arrangingCoins.arrangeCoins(6));
System.out.println(arrangingCoins.arrangeCoins(8));
System.out.println(arrangingCoins.arrangeCoins(2147483647));
}
}