> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-16-2022-441.md).

# 01/16/2022 441

Brutal force:

set row = 1, using  while loop: if n - row >= 0, n = n- row, row ++, return row -1;

Time space: O(sqrt(n)) Space O(1)

```
class Solution { 
    public int arrangeCoins(int n) {
         if(n < 1) return 0; 
         int row = 1; 
          while(n - row >= 0){ 
           n = n - row; 
           row++; }
    
    return row - 1 ;
    
}
```

}

method 2: binary search

For this question, we should know that 1 + 2 +3... + k = k(k+ 1)/2. So that we konw k(k+ 1)/2 <= n. Then we use binary search. set k first = middle value and compute the value with the formular above and compare its value with n, finally find the right value.&#x20;

Time O(LlogN) Space O(1)