Arranging coins

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.

Sample Input

7

Sample Output

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);
}

Output

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));
  }
}

Output

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))

Output

13

People are also reading:

• Monotonic Array
• Binary Gap
• Maximum Units
• Missing Numbers
• Mountain Array
• What is Pseudocode?
• Hybrid Quicksort Algorithm
• Quicksort using Dutch National Flag Algorithms
• Create a mirror of an m–ary Tree
• Maximum Product Subset Problem