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.

Discussion

First of all, let's reformulate the problem into mathematical format:

given a positive integer `n`, determine the largest integer `k` such that:

k (k + 1) / 2 <= n

Intuitively, we have k smaller than n, searching for the largest k, binary search would be our good old friend.

Solution

Our solution starts with a basic binary search setup, with the evaluation of the above formula.

Note that to prevent infinity loop issue, we limit our searching range by an extra 1 in every iteration.

And for the last case, we return tail instead of head as tail <= head after breaking the loop.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        head = 0
        tail = n

        while head <= tail:
            ptr = (tail + head) // 2
            temp = ptr * (ptr + 1) / 2

            if temp == n:
                return ptr

            elif temp < n:
                head = ptr + 1

            elif temp > n:
                tail = ptr - 1

        return tail

Complexity Analysis

• Time Complexity: O(log(n)), for binary search algorithm.
• Space Complexity: O(1), as no special data is cached in memory.