# 441. Arranging Coins

Easy
You have `n` coins and you want to build a staircase with these coins. The staircase consists of `k` rows where the `ith` row has exactly `i` coins. The last row of the staircase may be incomplete.
Given the integer `n`, return the number of complete rows of the staircase you will build.
Example 1: Input: n = 5
Output:
2
Explanation:
Because the 3rd row is incomplete, we return 2.
Example 2: Input: n = 8
Output:
3
Explanation:
Because the 4th row is incomplete, we return 3.
Constraints:
• `1 <= n <= 231 - 1`

### 解題

Binary search + 總和公式 ： 1~k的和等於 k(1+k)/2
func arrangeCoins(n int) int {
if n == 1 { return 1 }
if n == 2 { return 1 }
if n == 3 { return 2 }
left := 0
right := n/2
res := 0
for left <= right {
mid := left + (right - left)/2
sum := mid*(mid+1)/2
if sum == n {
return mid
} else if sum > n {
right = mid - 1
} else {
res = mid
left = mid + 1
}
}
return res
}
{"ft_lang_label":"__label__en","ft_lang_prob":0.5997742,"math_prob":0.99878055,"size":881,"snap":"2023-14-2023-23","text_gpt3_token_len":293,"char_repetition_ratio":0.12770809,"word_repetition_ratio":0.041666668,"special_character_ratio":0.36095345,"punctuation_ratio":0.12698413,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99871325,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,4,null,3,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-05-31T11:06:06Z\",\"WARC-Record-ID\":\"<urn:uuid:60ea651c-4cdb-4f71-a8a2-ac6d1aa186e6>\",\"Content-Length\":\"579594\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6a6a19cc-d868-4a28-bac8-c9c43ca742e6>\",\"WARC-Concurrent-To\":\"<urn:uuid:56a46558-4495-478f-84f0-11d3ee1aa6c1>\",\"WARC-IP-Address\":\"104.18.3.117\",\"WARC-Target-URI\":\"https://leetcode.weippig.com/golang/441.-arranging-coins\",\"WARC-Payload-Digest\":\"sha1:26TZQK7WPKY4XFOI7I3RBGRUZ7HQVJ6P\",\"WARC-Block-Digest\":\"sha1:PKQSJS7GLZMMWRFPEBDS322MCVJT6Y2Q\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224646457.49_warc_CC-MAIN-20230531090221-20230531120221-00251.warc.gz\"}"}