We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Arranging Coins

Number: 441

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Adobe, Amazon, GoDaddy

Problem Description

Given n coins, determine the number of complete rows that can be formed in a staircase where the i-th row has exactly i coins. A row is considered complete only if it contains exactly i coins.

Key Insights

  • The problem reduces to finding the maximum integer k such that the sum of the first k natural numbers (k*(k+1)/2) is less than or equal to n.
  • A mathematical derivation leads to a quadratic inequality; however, a binary search approach efficiently finds k.
  • Binary search helps avoid potential pitfalls with floating-point precision when using the direct mathematical formula.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

We utilize a binary search approach to determine the maximum integer k for which the inequality k*(k+1)/2 ≤ n holds true. Start with low = 0 and high = n. Calculate the mid value and the sum of the first mid natural numbers. If this sum is less than or equal to n, we can try for a larger k; otherwise, reduce the high bound. This efficiently converges to the correct answer.

Code Solutions

# Python solution for Arranging Coins

def arrangeCoins(n: int) -> int:
    low, high = 0, n  # Initialize the search space from 0 to n

    while low <= high:
        mid = (low + high) // 2  # Choose the middle value
        current_sum = mid * (mid + 1) // 2  # Calculate sum of first mid natural numbers
        
        # Check if current sum is within the allowed number of coins
        if current_sum == n:
            return mid  # Found exact match
        elif current_sum < n:
            low = mid + 1  # Try to find a larger k
        else:
            high = mid - 1  # Too many coins used, decrease k
            
    # Return the largest k that does not exceed n coins
    return high

# Example usage:
print(arrangeCoins(5))  # Expected output: 2
← Back to All Questions