• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode -441- Arranges coins

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

You have n coins and plan to arrange them in a ladder. For a ladder consisting of rows K, row I must have exactly I coins. The last row of the ladder may be incomplete.

Given a number n, calculate and return the total number of rows that can form a full stepped row.

 

Example 1:

Input: n = 5 Output: 2 Explanation: Return 2 because the third line is incomplete.Copy the code

Example 2:

Input: n = 8 Output: 3 Explanation: Return 3 because the fourth line is incomplete.Copy the code

Tip:

  • 1 <= n <=
    2 31 2^{31}     – 1

Idea 1: binary search

  • According to binary search 0-n satisfy the condition of the solution can be returned
  • Simple problem or simple problem phone code style is a bit messy
public int arrangeCoins(int n) {
    long l =1, r=n;
    while(l<r){
        long mid = (l - r +1) /2+r;

        if(mid*(mid-1) /2>n) r=mid-1;
        else l=mid;

    }
    return l*(l+1) /2==n? (int)l:(int)l-1;
}
Copy the code
  • Time complexity O(LGN)
  • Space complexity O(1)

Idea 2: Mathematical formulas

  • Of course, this kind of problem should be moved out of the immortal mathematics
  • I’m not going to write the root formula
public int arrangeCoins(int n) {
        return (int)((Math.sqrt(1 + 8.0 * n) - 1) / 2);
    }
Copy the code
  • Time complexity O(1)
  • Space complexity O(1)