Arranging coins

Posted in

Arranging coins
vinaykhatri

Vinay Khatri
Last updated on April 25, 2024

    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:

    Leave a Comment on this Post

    0 Comments