Simple Java 4-line solution using mathematics


  • 0
    Y

    O(1) time complexity

       // ((1 + k) * k) / 2 <= n To find the maximum k
        // (1 + k) * k <= 2 * n
        // so k = Math.sqrt(2 * n) - 1 or Math.sqrt(2 * n);
    

    // use long instead of int since you use 2 * int and int * int which will overflow

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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.