Arranging Coins - Practice Coding Problems

Arranging Coins - Problem

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the i-th row has exactly i coins.

The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Input & Output

Example 1 — Basic Case

$ Input: n = 5

› Output: 2

💡 Note: Row 1: 1 coin (4 left), Row 2: 2 coins (2 left), Row 3 needs 3 coins but only 2 left. So 2 complete rows.

Example 2 — Perfect Triangle

$ Input: n = 3

› Output: 2

💡 Note: Row 1: 1 coin (2 left), Row 2: 2 coins (0 left). Exactly 2 complete rows with no coins remaining.

Example 3 — Large Number

$ Input: n = 8

› Output: 3

💡 Note: Row 1: 1 coin, Row 2: 2 coins, Row 3: 3 coins (total 6), Row 4 needs 4 but only 2 left. So 3 complete rows.

Constraints

1 ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=5 coins to arrange

Build Staircase

Row 1: 1 coin, Row 2: 2 coins, Row 3 incomplete

Count Complete

Return 2 (number of complete rows)

Key Takeaway

🎯 Key Insight: Find largest k where triangular number k*(k+1)/2 ≤ n

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is recognizing this as finding the largest k where k*(k+1)/2 ≤ n. Best approach uses the mathematical formula k = ⌊(-1 + √(1 + 8n))/2⌋ for O(1) time. Binary search provides an intuitive O(log n) alternative.

Common Approaches

Approach	Time	Space	Notes
✓ Row by Row Counting	O(√n)	O(1)	Build rows one by one until we can't complete the next row
Binary Search on Answer	O(log n)	O(1)	Binary search on possible number of complete rows (1 to n)
Mathematical Formula	O(1)	O(1)	Use quadratic formula to solve k*(k+1)/2 ≤ n directly

Row by Row Counting — Algorithm Steps

Step 1: Start with row 1, subtract 1 coin
Step 2: Move to next row, subtract required coins
Step 3: Continue until remaining coins < next row size

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n=5 coins, build row 1 (1 coin)

Continue

4 coins left, build row 2 (2 coins), 2 coins left

Stop

2 coins left, can't complete row 3 (needs 3), return 2

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    int row = 1;
    while (n >= row) {
        n -= row;
        row++;
    }
    return row - 1;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

We iterate through rows 1, 2, 3, ..., k where k ≈ √(2n)

✓ Linear Growth

Space Complexity

O(1)

Only use a few variables to track current row and remaining coins

✓ Linear Space

111.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Row by Row Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler