Solution Approach

We use binary search to find the largest number of complete rows k where k * (k + 1) / 2 ≤ n.

Understanding the feasible function: For a given number of rows k, we need k * (k + 1) / 2 coins to complete all rows. The feasible condition is:

• feasible(k) = true if k * (k + 1) / 2 ≤ n

This creates a boolean pattern:

k:         1     2     3     4     5     ...
coins:     1     3     6    10    15     ...
feasible:  true  true  true  true  false  ... (when n = 11)

We want to find the last true position, which is equivalent to finding the first k where k * (k + 1) / 2 > n.

Binary Search Template (finding first false, then subtract 1):

left, right = 1, n
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if mid * (mid + 1) // 2 <= n:  # feasible
        first_true_index = mid
        left = mid + 1  # Look for larger k
    else:
        right = mid - 1  # k is too large

return first_true_index

Why this works:

• If k rows can be formed with n coins, we record it and try larger values
• If k rows need more coins than n, we try smaller values
• The answer is the largest k where the condition is true

Time Complexity: O(log n) - Binary search over the range [1, n] Space Complexity: O(1) - Only constant extra space used

Example Walkthrough

Let's walk through the solution with n = 11 coins using binary search.

Step 1: Set up binary search

• left = 1, right = 11
• first_true_index = -1

Step 2: Binary search iterations

Iteration 1: left=1, right=11

• mid = (1 + 11) // 2 = 6
• Check: 6 * 7 / 2 = 21 > 11 → not feasible
• right = 5

Iteration 2: left=1, right=5

• mid = (1 + 5) // 2 = 3
• Check: 3 * 4 / 2 = 6 ≤ 11 → feasible
• first_true_index = 3, left = 4

Iteration 3: left=4, right=5

• mid = (4 + 5) // 2 = 4
• Check: 4 * 5 / 2 = 10 ≤ 11 → feasible
• first_true_index = 4, left = 5

Iteration 4: left=5, right=5

• mid = (5 + 5) // 2 = 5
• Check: 5 * 6 / 2 = 15 > 11 → not feasible
• right = 4

Loop ends: left = 5 > right = 4

Answer: first_true_index = 4

Verification: With 4 complete rows, we use:

• Row 1: 1 coin
• Row 2: 2 coins
• Row 3: 3 coins
• Row 4: 4 coins
• Total: 1 + 2 + 3 + 4 = 10 coins

We have 11 coins, so 4 rows use 10, leaving 1 coin. Row 5 would need 5 coins, so we can't complete it.

Time and Space Complexity

Time Complexity: O(log n)

The solution uses binary search over the range [1, n]. In each iteration:

• We calculate the mid value and check if mid * (mid + 1) / 2 ≤ n
• Based on the result, we halve the search space

The number of iterations is proportional to log n, and each iteration performs constant-time arithmetic operations.

Space Complexity: O(1)

The solution only uses a constant amount of extra space for variables (left, right, mid, firstTrueIndex, coinsNeeded). No additional data structures or recursive calls are used.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with left = mid for finding the last true position, which can cause infinite loops.

Incorrect:

while left < right:
    mid = (left + right + 1) // 2  # Need +1 to avoid infinite loop
    if mid * (mid + 1) // 2 <= n:
        left = mid
    else:
        right = mid - 1
return left

Correct (template-compliant):

first_true_index = 0
while left <= right:
    mid = (left + right) // 2
    if mid * (mid + 1) // 2 <= n:
        first_true_index = mid
        left = mid + 1
    else:
        right = mid - 1
return first_true_index

The template approach avoids the need for +1 adjustments and infinite loop concerns.

2. Integer Overflow in Sum Calculation

When calculating mid * (mid + 1) / 2 for large values of mid, integer overflow can occur.

Incorrect (in Java/C++):

int mid = (left + right) / 2;
int sum = mid * (mid + 1) / 2;  // Overflow when mid > ~46340

Correct:

long mid = left + (right - left) / 2;
long sum = mid * (mid + 1) / 2;

Use long types for intermediate calculations when n can be large.

3. Off-by-One in Search Space

Setting incorrect initial bounds.

Incorrect:

left, right = 0, n  # left should start at 1 (at least 1 row possible for n >= 1)

Correct:

left, right = 1, n
first_true_index = 0  # Handle n = 0 edge case

4. Forgetting Edge Case n = 0

When n = 0, no rows can be formed. Initialize first_true_index = 0 to handle this case correctly.