[LeetCode] Arranging Coins

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.

Example:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Approach: If we see look at the problem closely, we will notice that if kth row can be formed using n coins then:

1 + 2 + 3 + ... + k <= n

(k * (k + 1)) / 2 <= n

k * (k  + 1) <= 2 * n

k^2 + k <= 2 * n

k^2 + 2*1/2*k + 1/4 <= 2 * n + 1/4

(k + 1/2)^2 <= 2 * n + 1/4

k + 1/2  <= Sqrt (2 * n + 1/4)

k <= Sqrt (2 * n + 1/4) + 1/2

k = Floor (Sqrt (2 * n + 1/4) + 1/2) 

So now using the above formula, we can get the number of rows can be formed in constant time. We just need to take care of the overflow condition of 2 * n. That is all!

Implementation in C#:

        public static int ArrangeCoins(int n)

        {

            return (int)(Math.Sqrt(2 * (long)n + 0.25) - 0.5);

        }

Complexity: O(1)