441. Arranging Coins - Explanation

Description

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Return the number of complete rows of the staircase you will build.

Example 1:

#
# #
#

Input: n = 4

Output: 2

Example 2:

#
# #
# # #
# # #

Input: n = 9

Output: 3

Constraints:
1 <= n <= ((2^31) - 1)

Topics

Math Binary Search

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search - Searching for the optimal value in a sorted search space
Arithmetic Series - The formula for sum of first k integers: k * (k + 1) / 2
Basic Math - Solving quadratic inequalities and using the quadratic formula

1. Brute Force

Intuition

We are building a staircase where row 1 needs 1 coin, row 2 needs 2 coins, and so on. The question is: how many complete rows can we build with n coins?

The simplest approach is to simulate the process. Keep adding rows one by one, subtracting the required coins from n until we cannot complete another row.

Algorithm

Initialize row = 0.
While we have enough coins for the next row (n > row):
- Increment row.
- Subtract row coins from n.
Return row as the number of complete rows.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        row = 0
        while n - row > 0:
            row += 1
            n -= row
        return row

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    arrangeCoins(n) {
        let row = 0;
        while (n - row > 0) {
            row++;
            n -= row;
        }
        return row;
    }
}

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var n = n
        var row = 0
        while n - row > 0 {
            row += 1
            n -= row
        }
        return row
    }
}

Time & Space Complexity

Time complexity: $O(\sqrt {n})$
Space complexity: $O(1)$

2. Binary Search

Intuition

Building rows one by one is slow for large n. Instead, we can use the formula for the sum of first k integers: k * (k + 1) / 2. If this sum is at most n, we can build k complete rows.

This creates a monotonic condition perfect for binary search. We search for the largest k such that k * (k + 1) / 2 <= n.

Algorithm

Set search bounds: l = 1 and r = n.
While l <= r:
- Compute mid and calculate coins needed for mid rows.
- If coins needed exceeds n, search the left half.
- Otherwise, update the result and search the right half.
Return the maximum valid k.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        l, r = 1, n
        res = 0

        while l <= r:
            mid = (l + r) // 2
            coins = (mid * (mid + 1)) // 2
            if coins > n:
                r = mid - 1
            else:
                l = mid + 1
                res = max(res, mid)

        return res

public class Solution {
    public int arrangeCoins(int n) {
        int l = 1, r = n, res = 0;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            long coins = (long) mid * (mid + 1) / 2;
            if (coins > n) {
                r = mid - 1;
            } else {
                l = mid + 1;
                res = Math.max(res, mid);
            }
        }

        return res;
    }
}

class Solution {
public:
    int arrangeCoins(int n) {
        long long l = 1, r = n, res = 0;

        while (l <= r) {
            long long mid = l + (r - l) / 2;
            long long coins = (mid * (mid + 1)) / 2;
            if (coins > n) {
                r = mid - 1;
            } else {
                l = mid + 1;
                res = max(res, mid);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    arrangeCoins(n) {
        let l = 1,
            r = n,
            res = 0;

        while (l <= r) {
            let mid = Math.floor((l + r) / 2);
            let coins = (mid * (mid + 1)) / 2;
            if (coins > n) {
                r = mid - 1;
            } else {
                l = mid + 1;
                res = Math.max(res, mid);
            }
        }

        return res;
    }
}

public class Solution {
    public int ArrangeCoins(int n) {
        int l = 1, r = n;
        int res = 0;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            long coins = (long)mid * (mid + 1) / 2;

            if (coins > n) {
                r = mid - 1;
            } else {
                res = Math.Max(res, mid);
                l = mid + 1;
            }
        }

        return res;
    }
}

func arrangeCoins(n int) int {
    l, r := 1, n
    res := 0

    for l <= r {
        mid := l + (r-l)/2
        coins := int64(mid) * int64(mid+1) / 2
        if coins > int64(n) {
            r = mid - 1
        } else {
            l = mid + 1
            if mid > res {
                res = mid
            }
        }
    }

    return res
}

class Solution {
    fun arrangeCoins(n: Int): Int {
        var l = 1
        var r = n
        var res = 0

        while (l <= r) {
            val mid = l + (r - l) / 2
            val coins = mid.toLong() * (mid + 1) / 2
            if (coins > n) {
                r = mid - 1
            } else {
                l = mid + 1
                res = maxOf(res, mid)
            }
        }

        return res
    }
}

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var l = 1
        var r = n
        var res = 0

        while l <= r {
            let mid = l + (r - l) / 2
            let coins = mid * (mid + 1) / 2
            if coins > n {
                r = mid - 1
            } else {
                l = mid + 1
                res = max(res, mid)
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Binary Search (Optimal)

Intuition

We can optimize the binary search by tightening the upper bound. Since k * (k + 1) / 2 <= n, we know k is roughly sqrt(2n). A safe upper bound is n / 2 + 1 for n > 3, which reduces the search space.

We also simplify the binary search by finding the first k where the condition fails, then returning k - 1.

Algorithm

Handle small cases: if n <= 3, return 1 for n = 1 and n - 1 otherwise.
Set l = 1 and r = n / 2 + 1.
Use binary search to find the smallest k where coins exceed n.
Return l - 1.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        if n <= 3:
            return n if n == 1 else n - 1

        l, r = 1, (n // 2) + 1
        while l < r:
            mid = (l + r) // 2
            if (mid * (mid + 1)) // 2 <= n:
                l = mid + 1
            else:
                r = mid

        return l - 1

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    arrangeCoins(n) {
        if (n <= 3) {
            return n == 1 ? 1 : n - 1;
        }

        let l = 1,
            r = n / 2 + 1;
        while (l < r) {
            let mid = Math.floor((l + r) / 2);
            let coins = (mid * (mid + 1)) / 2;
            if (coins <= n) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return l - 1;
    }
}

func arrangeCoins(n int) int {
    if n <= 3 {
        if n == 1 {
            return 1
        }
        return n - 1
    }

    l, r := 1, n/2+1
    for l < r {
        mid := (l + r) / 2
        coins := int64(mid) * int64(mid+1) / 2
        if coins <= int64(n) {
            l = mid + 1
        } else {
            r = mid
        }
    }

    return l - 1
}

class Solution {
    fun arrangeCoins(n: Int): Int {
        if (n <= 3) {
            return if (n == 1) 1 else n - 1
        }

        var l = 1
        var r = n / 2 + 1
        while (l < r) {
            val mid = (l + r) / 2
            val coins = mid.toLong() * (mid + 1) / 2
            if (coins <= n) {
                l = mid + 1
            } else {
                r = mid
            }
        }

        return l - 1
    }
}

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        if n <= 3 {
            return n == 1 ? 1 : n - 1
        }

        var l = 1
        var r = n / 2 + 1
        while l < r {
            let mid = (l + r) / 2
            let coins = mid * (mid + 1) / 2
            if coins <= n {
                l = mid + 1
            } else {
                r = mid
            }
        }

        return l - 1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Bit Manipulation

Intuition

We can build the answer bit by bit, from the most significant bit down. For each bit position, we tentatively set it and check if the resulting number of rows is valid. If valid, we keep the bit; otherwise, we clear it.

Since n fits in 32 bits and k is roughly sqrt(n), we only need about 16 bits to represent the answer.

Algorithm

Start with a mask at the highest relevant bit (bit 15).
For each bit from high to low:
- Set the bit in rows.
- Calculate coins needed for rows rows.
- If it exceeds n, clear the bit.
- Shift mask right.
Return rows.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        mask = 1 << 15
        rows = 0
        while mask > 0:
            rows |= mask
            coins = rows * (rows + 1) // 2
            if coins > n:
                rows ^= mask
            mask >>= 1
        return rows

public class Solution {
    public int arrangeCoins(int n) {
        int mask = 1 << 15;
        int rows = 0;
        while (mask > 0) {
            rows |= mask;
            long coins = (long) rows * (rows + 1) / 2;
            if (coins > n) {
                rows ^= mask;
            }
            mask >>= 1;
        }
        return rows;
    }
}

class Solution {
public:
    int arrangeCoins(int n) {
        int mask = 1 << 15;
        int rows = 0;
        while (mask > 0) {
            rows |= mask;
            long long coins = (long long) rows * (rows + 1) / 2;
            if (coins > n) {
                rows ^= mask;
            }
            mask >>= 1;
        }
        return rows;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    arrangeCoins(n) {
        let mask = 1 << 15;
        let rows = 0;
        while (mask > 0) {
            rows |= mask;
            let coins = (rows * (rows + 1)) / 2;
            if (coins > n) {
                rows ^= mask;
            }
            mask >>= 1;
        }
        return rows;
    }
}

public class Solution {
    public int ArrangeCoins(int n) {
        int mask = 1 << 15;
        int rows = 0;

        while (mask > 0) {
            rows |= mask;
            long coins = (long)rows * (rows + 1) / 2;
            if (coins > n) {
                rows ^= mask;
            }
            mask >>= 1;
        }

        return rows;
    }
}

func arrangeCoins(n int) int {
    mask := 1 << 15
    rows := 0
    for mask > 0 {
        rows |= mask
        coins := int64(rows) * int64(rows+1) / 2
        if coins > int64(n) {
            rows ^= mask
        }
        mask >>= 1
    }
    return rows
}

class Solution {
    fun arrangeCoins(n: Int): Int {
        var mask = 1 shl 15
        var rows = 0
        while (mask > 0) {
            rows = rows or mask
            val coins = rows.toLong() * (rows + 1) / 2
            if (coins > n) {
                rows = rows xor mask
            }
            mask = mask shr 1
        }
        return rows
    }
}

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var mask = 1 << 15
        var rows = 0
        while mask > 0 {
            rows |= mask
            let coins = rows * (rows + 1) / 2
            if coins > n {
                rows ^= mask
            }
            mask >>= 1
        }
        return rows
    }
}

Time & Space Complexity

Time complexity: $O(1)$ since we iterate $15$ times.
Space complexity: $O(1)$

5. Math

Intuition

We can solve this directly with algebra. We need the largest k where k * (k + 1) / 2 <= n. Rearranging: k^2 + k - 2n <= 0. Using the quadratic formula, k = (-1 + sqrt(1 + 8n)) / 2.

Simplifying gives us k = sqrt(2n + 0.25) - 0.5. We take the floor of this value to get the answer.

Algorithm

Compute sqrt(2 * n + 0.25) - 0.5.
Return the integer part.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(sqrt(2 * n + 0.25) - 0.5)

Time & Space Complexity

Time complexity: $O(1)$ or $O(\sqrt {n})$ depending on the language.
Space complexity: $O(1)$

Common Pitfalls

Integer Overflow When Computing mid * (mid + 1)

When using binary search, computing mid * (mid + 1) can overflow for large values of mid if using 32-bit integers. Always cast to a larger type before multiplication.

// Wrong: overflow when mid is large
int coins = mid * (mid + 1) / 2;

// Correct: cast to long first
long coins = (long) mid * (mid + 1) / 2;

Off-by-One Error in the Result

The formula k * (k + 1) / 2 gives the total coins needed for k complete rows. A common mistake is returning the wrong value when the sum exactly equals n or when determining whether to include the current row.

# Wrong: returning l instead of l - 1 after binary search
while l < r:
    mid = (l + r) // 2
    if mid * (mid + 1) // 2 <= n:
        l = mid + 1
    else:
        r = mid
return l  # Should be l - 1