Category: Easy
Problem
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.
https://leetcode.com/problems/arranging-coins/
Examples:
Example 1
1 2 3 4 5 6 7 8 | n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2. |
Example 2
1 2 3 4 5 6 7 8 9 | n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3. |
Solution Approach
This question looks pretty easy in the first glance. Although it is easy I will show fast mathematical techniques to solve questions like these.
Arithmetic Progression
If you look at the question and the examples carefully you will detect a pattern in the number of steps. It always starts with 1 and 1 is incremented every time until it reaches a point when there are no coins for further steps or there are not enough coins for the next step. This forms an AP or Arithmetic Progression with initial value as 1 and step as 1. If you are not familiar with AP you can check here. Now to solve the problem using AP just keep on subtracting step value from N and incrementing step by 1 until the step value is greater than the value of N.
Completing the square
We can also use completing the square technique which is used in quadratic equations to solve the problem. Learn more about it here.
To solve the problem an equation is given in the question which we will use and complete the square for k.
(K(K+1) / 2) <= N
Using completing the square technique on it we get
(k + 0.5)2 – 0.25 <= 2*n
After solving this equation we will get
K = Sqrt(2*N + 0.25) – 0.5
Now using this equation we can get the answer directly.
Solution Code
Arithmetic Progression
1 2 3 4 5 6 7 8 9 10 | class Solution { public int arrangeCoins(int n) { int step = 1; while(n>=step){ n-=step; // n = n-step; step++; } return step-1; } } |
Completing the square
1 2 3 4 5 | class Solution { public int arrangeCoins(int n) { return (int)(Math.sqrt(2 * (long)n + 0.25) - 0.5); } } |
For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂