LeetCode Challenge July Begins

Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every kth 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:

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

Example 2:

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

Brute Force

1. Simply find out the sum at each level, if the sum ≤ n
2. Return level
3. Time complexity O(n^.5)
4. Space complexity O(1)

Method 2: Binary Search

1. Since each level contains the corresponding number of coins, we can use Gauss formula to find how many levels we need
2. Let’s assume that the we need x level, we will have x(x + 1)/2 <= n
3. We declare low = 1 and high = n and perform a binary search until we have reached the end

We have three cases

1. If mid(mid + 1) = 2n, we can return it
2. If mid(mid + 1) < 2n, we should decrease the range by low = mid + 1
3. If mid(mid + 1) > 2n, we should decrease the range by high = mid — 1

In the end, we can put case 1 and 2 together, since at the end we want to return the lower one, which is the high variable

1. Time complexity O(log(n))
2. Space complexity O(1)