441. Arranging Coins

Problem Description

In this problem, you are given n coins, and your goal is to create a staircase in which each row has a specific number of coins. For the first row, you place 1 coin, for the second row, 2 coins, for the third row, 3 coins, and so on, such that the ith row contains exactly i coins. The challenge is that you may not have a sufficient number of coins to complete the last row of the staircase, meaning the last row can be incomplete. The task is to find out how many complete rows you can form with the n coins you have.

Intuition

The solution is based on finding a formula that relates the number of coins n to the number of complete rows k in the staircase. Mathematically, if we were to have k complete rows, the total number of coins used would be the sum of the first k positive integers, which is often expressed as k(k + 1)/2. The problem is essentially asking us to solve for k given the sum n. This sum can be expressed as a quadratic equation in terms of k:

1k^2 + k - 2n = 0

By solving this quadratic equation for k (and considering only the positive root, since the number of rows cannot be negative), we arrive at the formula used in the solution:

1k = (-1 + sqrt(1 + 8n)) / 2

However, in implementation, this formula has been modified slightly using mathematical manipulations to:

1k = sqrt(2) * sqrt(n + 0.125) - 0.5

This form is mathematically equivalent to the formula derived directly from solving the quadratic equation. Both expressions will yield the correct number of complete rows k. The choice of this particular expression for k could be to reduce computational errors that might arise from calculating the large values of n when directly using the standard quadratic formula. The final step is then to take the integer part of the result, since the number of complete rows has to be a whole number.

Learn more about Math and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Solution Approach

The implementation of the solution uses the Python [math](/problems/math-basics) module to perform the square root operation. The code consists of a single function arrangeCoins within the Solution class.

Here is the breakdown of the implementation steps:

The function arrangeCoins receives an integer n, which represents the number of coins.
To compute the number of complete rows k, the formula from our intuition section is converted into Python code:
```
1k = int([math](/problems/math-basics).sqrt(2) * math.sqrt(n + 0.125) - 0.5)
```
This line makes use of the math.sqrt method to calculate the square root. The multiplication by math.sqrt(2) and addition followed by subtraction takes into account the coefficient and constants from the rearranged quadratic formula.
The int() function is used to convert the resulting float number into an integer. This is necessary because the number of complete rows cannot be a fraction; if the final row is not full, it does not count as a complete row.

No additional data structures or complex algorithms are needed since the solution is primarily mathematical and does not require iteration or recursion. The key pattern is to apply the mathematical insight that the sum of the first k positive integers forms an arithmetic progression, and the reverse engineering of this progression to find k given the sum n.

This approach is highly efficient as it runs in constant time O(1), meaning it will have the same performance regardless of the size of n.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Example Walkthrough

Let's say we are given n = 8 coins, and we need to find out how many complete rows we can form in our staircase.

Step by step, using the solution approach:

We start with our formula that relates the total number of coins n to the number of complete rows k:
```
1k^2 + k - 2n = 0
```

Using the provided optimization in the formula (sqrt(2) * sqrt(n + 0.125) - 0.5), let's insert our n = 8 into the equation:

1k = sqrt(2) * sqrt(8 + 0.125) - 0.5
2k = sqrt(2) * sqrt(8.125) - 0.5
3k ≈ sqrt(2) * 2.85 - 0.5
4k ≈ 4.03 - 0.5
5k ≈ 3.53

The final step is to take the integer part of k because rows can only have whole coins:
```
1k = int(3.53)
2k = 3
```

So, with our 8 coins, we can create 3 complete rows in our staircase. The first row will have 1 coin, the second will have 2 coins, the third will have 3 coins, and there will be 2 coins left that are insufficient to form another complete row (which would require 4 coins). Therefore, the answer is 3 complete rows for n = 8 coins.

Solution Implementation

1import math
2
3class Solution:
4    def arrangeCoins(self, n: int) -> int:
5        # Since the problem can be reduced to finding a solution to the
6        # quadratic equation k(k + 1)/2 <= n, where k is the number of
7        # complete rows of the coin staircase; we can find the positive
8        # root of the equation k^2 + k - 2n = 0 and adjust for integer
9        # value since we cannot have a fraction of a row.
10
11        # Calculating the number using the quadratic formula part by part
12        # The constant 0.125 is added to n for compensating the increment by 0.5
13        # since (k + 0.5)^2 = k^2 + k + 0.25 and we need to subtract the 0.25.
14        # Hence, n + 0.125 is used so that after subtracting 0.5 we are left
15        # with k(k + 1) / 2, which is our original formula.
16        raw_value = math.sqrt(2) * math.sqrt(n + 0.125) - 0.5
17      
18        # Since the number of complete rows must be an integer, we take the
19        # integer part of the calculated value
20        complete_rows = int(raw_value)
21        return complete_rows
22
23# Example usage:
24# solution = Solution()
25# number_of_coins = 5
26# print(solution.arrangeCoins(number_of_coins))  # Output: 2
27

1class Solution {
2
3    /**
4     * This method finds the maximum number of complete rows of coins that can be formed.
5     * Each row of coins consists of 1 more coin than the previous row. The number of
6     * coins used in row i is i, and coins are used starting from row 1 up to the row
7     * that can be completed.
8     *
9     * @param n The total number of coins available for arranging in rows.
10     * @return The maximum number of complete rows that can be formed with n coins.
11     */
12    public int arrangeCoins(int n) {
13        // The mathematical solution is derived from the formula for the sum of
14        // an arithmetic series: (x * (x + 1)) / 2 <= n, solving for the positive
15        // root using the quadratic formula gives us x. Since we can only have a
16        // whole number of rows, we take the floor of the result by casting it to
17        // an integer
18      
19        // The 0.125 is added to handle the rounding caused by integer division
20        // and ensures we get the correct row count even when x is not a whole number.
21        return (int) (Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
22    }
23}
24

1#include <iostream>
2
3// Define LL as an alias for long to use as a larger integer type.
4using LL = long;
5
6class Solution {
7public:
8    // This function calculates the maximum number of complete rows of a staircase
9    // you can build with n coins.
10    int arrangeCoins(int n) {
11        // Initialize the search interval.
12        LL left = 1, right = n;
13        // Run a binary search to find the maximum k rows that can be formed.
14        while (left < right) {
15            // Compute the middle point, be careful with overflow.
16            LL mid = left + (right - left) / 2 + 1;
17            // Sum of arithmetic series to find total coins used by k rows.
18            LL totalCoinsUsed = mid * (mid + 1) / 2;
19            // If the total coins used by k rows is more than n, look in the lower half.
20            if (n < totalCoinsUsed) {
21                right = mid - 1;
22            } else { 
23                // Otherwise, look in the upper half.
24                left = mid;
25            }
26        }
27        // Return the maximum number of complete rows that can be built.
28        return left;
29    }
30};
31

1// Define a type alias 'LL' for 'number' to represent a large integer type.
2type LL = number;
3
4// This function calculates the maximum number of complete rows of a staircase
5// that can be built with `n` coins.
6function arrangeCoins(n: number): number {
7    // Initialize the search interval.
8    let left: LL = 1, right: LL = n;
9    // Run a binary search to find the maximum `k` rows that can be formed.
10    while (left < right) {
11        // Compute the middle point, being careful to avoid overflow.
12        let mid: LL = left + Math.floor((right - left) / 2) + 1;
13        // Use the sum of arithmetic series formula to find the total coins used by `k` rows.
14        let totalCoinsUsed: LL = mid * (mid + 1) / 2;
15        // If the total coins used by `k` rows is more than `n`, search in the lower half.
16        if (n < totalCoinsUsed) {
17            right = mid - 1;
18        } else {
19            // Otherwise, search in the upper half.
20            left = mid;
21        }
22    }
23    // Return the maximum number of complete rows that can be built.
24    return left;
25}
26

Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Time and Space Complexity

The time complexity of the code is O(1) because the operations consist of a fixed number of mathematical computations that do not depend on the size of the input n.

The space complexity of the code is also O(1) since the algorithm uses a constant amount of space regardless of the input size. Variables used to store the calculations do not scale with n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

441. Arranging Coins

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings