สมมติว่าเรามีเหรียญ n เหรียญที่เราต้องการสร้างเป็นรูปบันได แถวที่ k ทุกแถวต้องมีเหรียญ k เหมือนกัน ดังนั้นหากเรามี n เราก็ต้องหาจำนวนแถวบันไดทั้งหมดที่สามารถเกิดขึ้นได้
ดังนั้น หากอินพุตเท่ากับ 5 เอาต์พุตจะเป็น 2 เนื่องจากการใช้ 5 เหรียญ เราสามารถสร้าง starecase เต็มสองแถว อันสุดท้ายต้องการสามแถว แต่เราต้องเหลือ 2 -
* ** **
สามารถทำได้โดยตรงโดยใช้สูตรนี้ -
$$\frac{\sqrt{(8n+1)}-1}{2}$$
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int arrangeCoins(int n) {
return (sqrt(8*(long long)n+1)-1)/2;
}
};
main(){
Solution ob;
cout << (ob.arrangeCoins(13));
} อินพุต
13
ผลลัพธ์
4
