Arranging Coins - Leetcode Solution

Problem statement:

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. Given n, find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1: Input: n = 5 Output: 2 Explanation: The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2.

Example 2: Input: n = 8 Output: 3 Explanation: The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.

Solution: The problem can be solved using a simple approach of iterating over the rows and checking if the number of coins left is greater than or equal to the number of coins required for the current row. This can be done by subtracting the number of coins required for the current row from the total number of coins and checking if the result is greater than or equal to the number of coins required for the next row. If this condition is true, we continue with the next row, else we stop and return the current row number.

Algorithm:

1. Initialize row number k as 1.
2. Subtract k from n and check if the result is greater than or equal to k+1. If true, set n to the result and increment row number k. If false, return k.
3. Repeat step 2 until n is less than k+1.
4. Return k-1 as the final result.

Code:

class Solution { public: int arrangeCoins(int n) { int k = 1; while (n >= k+1) { n -= k; k++; } return k-1; } };

Time Complexity: The time complexity of the above algorithm is O(sqrt(n)).

Space Complexity: The space complexity of the above algorithm is O(1).

Summary: The problem of arranging coins can be solved by iterating over the rows and checking if the number of coins is sufficient to form the current row. The time complexity of the algorithm is O(sqrt(n)) and the space complexity is O(1).

1