Easy C++ solution

  • 0

    From the question we know we need to add one and only one coin for each additional line. However, we have to make sure the total number of coins we used is no bigger than the given number n.

    Let's run few examples:
    if n = 0, then we have to return 0.
    if n = 1, then we can only have 1 line.
    if n = 2, we can have 2 lines, but the second line will not be a completed line. So we still need to return 1.

    Thus, we can derive the first condition:
    if (n < 2) return n; if (n == 2) return 1;

    Following this logic, we can add more coins:
    if given 3 coins, we will have 2 completed lines (1 coin on the first line, 2 coins on the second line).

    and so on....

    If you really walk through the above procedure, you will notice that the line number and the number of coins will have such relationship:

    coin numbers: 0 1 2 3 4 5 6 7 8 9 10...
    line numbers: 0 1 1 2 2 2 3 3 3 3 4...

    With a little math intuition, we can derive that for a given line number x, we will have x + 1 number that will return this line number as the final answer.

    Thus the only work we need to do is that we need to use this relationship to find where the given number n belongs to. This is relationship can be derived as:
    if (total_number_covered >= n) return the last line number

    Integrate everything together:

    class Solution {
        int arrangeCoins(int n) {
            if (n < 2) return n;
            long number_sums = 0;
            for (int i = 1; ; i++) {
                number_sums += i + 1;
                if (number_sums >= n) return i;

    Notice that: I get rid of the condition if (n == 2) return 1; as the loop already takes care of it.
    Notice again: the number_sums is long type to avoid overflow.

Log in to reply

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