Table of Contents

## Problem Statement

The **Arranging Coins LeetCode Solution – **“Arranging Coins” asks you to build a staircase with these coins. The staircase consists of k rows, where ith row consists of exactly i coins. The last row of the staircase may not be complete.

For the given amount of coins, return the **number of complete rows** of the staircase we can build.

## Example:

Input: n = 5

Output: 2

Explanation:

- We can build the first two rows of the staircase completely since 1 + 2 < 5.
- The last row will be incomplete since the last row requires 3 coins and we have 5 coins in total.
- Hence, our answer is 2.

Input: n = 8

Output: 3

Explanation:

- We can build the first three rows of the staircase completely since 1 + 2 + 3 < 8.
- The last row will be incomplete since the last row requires 4 coins and we have 8 coins in total.
- Hence, our answer is 3.

## Approach

### Idea:

- The main idea to solve this problem is to use
**Maths**. We can also solve this problem using**Binary Search**and**Bit Manipulation**. - Here, we’ll be talking about the
**mathematical solution**to this problem, - Start checking our answer from 1 and claim if we have enough coins to build the first
**answer**amount of rows or not? - How to check if there are
*enough coins*to build the first x amount of rows?- To build first x amount of rows, required number of coins will be
**sum of 1 + 2 + 3 + … + x**. - If the above sum is less than or equal to the total number of coins available, then we check for the greater value of x otherwise,
- Return the current amount of rows as our answer.

- To build first x amount of rows, required number of coins will be

## Code

### Arranging Coins Leetcode C++ Solution:

class Solution { public: int arrangeCoins(int n) { int ans = 0; while((ans+1)*1LL*(ans+2)<=(long long)n*2){ ans++; } return ans; } };

### Arranging Coins Leetcode Java Solution:

class Solution { public int arrangeCoins(int n) { int ans = 1; while(n > 0){ ans++; n = n-ans; } return ans-1; } }

## Complexity Analysis for Arranging Coins Leetcode Solution

### Time Complexity

The time complexity of the above code is **O(sqrt(N))**.

### Space Complexity

The space complexity of the above code is **O(1) **since we are using constant extra space.