Blog

How to Solve Arranging Coins Problem — Leetcode #441

  • Post last modified:December 15, 2022
  • Reading time:3 mins read

Introduction

  • In this article we will solve leetcode # 441 using Binary Search Data Structure.

Problem Statement

  • We have been given n coins and we need to build staircase with these coins.
  • i th row will have exactly i coins except last row which might be incomplete.
  • Given the integer n we need to find out number of complete rows of staircase.

Solutions

  • We can solve this problem in 2 ways . Solution # 1 takes O(N) TC while solution #2 takes O(logn) solution

Solution #1 

  • At first, we can identify from the question is that each row requires coins based on its position. For example first row would need 1 coin, 2nd row would need 2coins and so on.
  • Then we can use this logic to get the number of rows that we can fill with coins.
  • Here we can see that we are iteration over n rows and subtracting each row from coins , once the remaining coins are less than 0 then we can safely return the i-1 as last completed rows.
class Solution {
    public int arrangeCoins(int n) {
        int coins = n;
        for(int i=1;i<=n;i++){
            coins=coins-i;
            if(coins<0){
                return i-1;
            }
        }
        
        return 1;
    }
}
@imsurajmishra

Time Complexity: O(N), where N is the number of iteration of the loop
Space Complexity: O(1) since we are using constant space

Solution #2:

  • We can optimize the complexity to O(LogN). We can use Binary Search to find out last row that we can fill completely with coins in hand.
  • It’s not super intuitive logic but good to understand.
  • First of all we need to revisit school maths where we learned the sum of natural numbers formula.
  • So sum of n natural numbers. = N*(N+1)/2. We will use this formula in our logic.
  • Since our coins are sorted and they vary from 1 to n coins. So we first find the mid point and calculate sum of mid numbers.
  • If sum of mid numbers is less than n coins then our solution lies to left side of the binary search otherwise it would lies to right side of the binary search window. and we compare res with curr sum of mid numbers to keep track of max rows we can fill.
  • Once binary search loop terminates we will have max result stored in the res variable
class Solution {
    public int arrangeCoins(int n) {
        return helper(n);
    }
    
    private int helper(int n){
        long l=1;
        long r=n;
        long res=0;
        
        while(l<=r){
            long mid = l+(r-l)/2;
            long sum = ((mid)*(mid+1))/2;
            if(sum>n){
                r=mid-1;
            }else{
                l=mid+1;
                res=Math.max(res,mid);
            }
        }
        
        return (int)res;
    }
}

Result

  • Our solution is accepted by Leetcode and passed all the test cases.

Conclusion

  • In this article we solved Leetcode 441 question of arranging coins. This question can be solved using O(N) TC and its very easy to come up with this solution. But we can also optimize the solution using binary search and reduce TC to O(Logn)

Bonus Tip

  • If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )
Tags: , , , ,

Leave a Reply