Leetcode 441: Arranging Coins

Leetcode 441: Arranging Coins

Category: Easy


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

Example 2

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

Completing the square

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 🙂

Leave a Comment

Your email address will not be published. Required fields are marked *