# Arranging coins

Posted in  Vinay Khatri
Last updated on December 7, 2023

## Problem

We've been given ‘n’ coins, and you're supposed to use them to build a staircase. The staircase is made up of a certain number of rows, with the ‘ith’ row containing exactly ‘i’ coins. The last row of the staircase may not have all the required coins Return the number of complete rows of the staircase you will build given the integer ‘n’. The value of ‘n’ can go upto 109.

`7`

`3`

#### Explanation

```C
C C
C C C
C```

We can see that only 3 levels are fully filled

## Approach

We will use Binary Search to solve this problem. Below is the algorithm to solve this problem.

1. Initialize the ‘low’ variable with 0 and ‘high’ with ‘n’.
2. Do the below steps while(low<=high)
3. Find the middle of these two variables: ‘mid’.
4. If mid*(mid+1)/2 is equal to ‘n’, return ‘mid’.
5. If mid*(mid+1)/2 is greater than ‘n’, search left space.
6. Else search right search space.
7. Return ‘high’ at the end of the function

## Complexity Analysis

The time complexity is O(log(N)) with no extra space required

### C++ Programming

```#include<iostream>
using namespace std;
typedef long long int ll;

// function to find maximum stairs that can be filled
int arrangeCoins(int n) {

// initialize 'low' and 'high'
int low = 0, high = n;

while (low <= high) {

// find middle of 'low' and 'high'
ll mid = (low + high) / 2;

// if the sum of first 'mid' terms is smaller or equal to 'n', search right half
if (mid * (mid + 1) <= (ll) 2 * ll(n)) low = mid + 1;

// else search left half
else high = mid - 1;
}

return low - 1;
}

int main() {
int n = 100;

cout << arrangeCoins(n);
}```

`13`

### Java Programming

```class Solution {
// function to find maximum stairs that can be filled
public static int arrangeCoins(int n) {

// initialize 'low' and 'high'
long low = 0;
long high = n;

while (low <= high) {

// find middle of 'low' and 'high'
long mid = low + (high - low) / 2;
long coins = mid * (mid + 1) / 2;

// if the coins are equal to 'n'
if (coins == n) {
return (int) mid;
}

// if the sum of first 'mid' terms is greater than 'n', search left space
if (n < coins) {
high = mid - 1;
}

// else search right subspace
else {
low = mid + 1;
}
}

return (int) high;
}

public static void main(String args[]) {

int n = 100;

System.out.print(arrangeCoins(n));
}
}```

`13`

### Python Programming

```# function to find maximum stairs that can be filled
def arrangeCoins(n):
# initialize 'low' and 'high'
low = 1
high = n

while low<=high:
# find middle of 'low' and 'high'
mid = low + (high-low)//2
coins = int(mid*(mid+1)/2)

# if the coins are equal to 'n'
if coins == n:
return mid

# if the sum of first 'mid' terms is smaller than 'n', search right space
if coins < n:
low = mid + 1

# else search left subspace
else:
high = mid - 1

return high

n = 100

print(arrangeCoins(n))```

`13`