Arranging Coins Leetcode Solution

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:

1. The main idea to solve this problem is to use Maths. We can also solve this problem using Binary Search and Bit Manipulation.
2. Here, we’ll be talking about the mathematical solution to this problem,
3. Start checking our answer from 1 and claim if we have enough coins to build the first answer amount of rows or not?
4. How to check if there are enough coins to build the first x amount of rows?
   1. To build first x amount of rows, required number of coins will be sum of 1 + 2 + 3 + … + x.
   2. 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,
   3. Return the current amount of rows as our answer.

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.