441. 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 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.

Problem Summary #

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

Solution Ideas #

• With n coins, arrange them in increasing order to build a staircase: the first level has one coin, the second level has two, …… the nth level needs n coins. Ask up to which level the n coins can be built?
• There are 2 solutions to this problem. The first solution is to solve the equation for X, (1+x)x/2 = n, namely x = floor(sqrt(2*n+1/4) - 1/2), and the second solution is simulation.

Code #

package leetcode

import "math"

// Solution 1 Mathematical formula
func arrangeCoins(n int) int {
	if n <= 0 {
		return 0
	}
	x := math.Sqrt(2*float64(n)+0.25) - 0.5
	return int(x)
}

// Solution 2 Simulation
func arrangeCoins1(n int) int {
	k := 1
	for n >= k {
		n -= k
		k++
	}
	return k - 1
}