Skip to main content

Binary Search

Arranging Coins Solution In C++/Java/Python/JS

Illustration of Problem Description with example
Illustration of Problem Description with example

Problem 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.
Given the integer n, return the number of complete rows of the staircase you will build.

Examples:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.

Constraints:

  • 1 <= n <= 231 - 1

Arranging Coins Description

We have n coins, and they need to be arranged in a staircase format. Each row of the staircase contains a number of coins equal to its row number. The 1st row requires 1 coin, the 2nd row requires 2 coins, the 3rd row requires 3 coins, and so on.
The process continues until there are not enough coins to complete the next row. The goal is to determine how many full rows can be formed using the given n coins.
Let's observe the pattern of the staircase and try to come up with Arranging Coins Solution.

Brute Force Approach

Intuition:

What is the best you can think of to solve the Arranging Coins Problem?...

A natural way to solve the problem is by iterating through the rows while deducting the required number of coins for each row.

Arranging Coins Solution

We start with n coins and begin placing them in rows, where the first row takes 1 coin, the second row takes 2 coins, the third row takes 3 coins, and so on.

After placing coins in each row, we subtract the used coins from the total. This process continues until the remaining coins are not enough to complete the next row.

The number of fully completed rows gives the final answer. This approach is simple and intuitive, but it may not be the most efficient for large values of n since it involves repeatedly subtracting coins.

Illustration of Brute Force Approach

Arranging Coins example

Step 1: Initialization

  • n = 15 (Total number of coins)
  • k = 1 (First row starts with 1 coin)

Step 2: Iterations

  1. First iteration:
    • k = 1
    • Check: n - k = 15 - 1 = 14 (still ≥ 0, continue)
    • Subtract k from n: n = 14
    • Increment k: k = 2
  3. Second iteration:
    • k = 2
    • Check: n - k = 14 - 2 = 12 (still ≥ 0, continue)
    • Subtract k from n: n = 12
    • Increment k: k = 3
  5. Third iteration:
    • k = 3
    • Check: n - k = 12 - 3 = 9 (still ≥ 0, continue)
    • Subtract k from n: n = 9
    • Increment k: k = 4
  7. Fourth iteration:
    • k = 4
    • Check: n - k = 9 - 4 = 5 (still ≥ 0, continue)
    • Subtract k from n: n = 5
    • Increment k: k = 5
  9. Fifth iteration:
    • k = 5
    • Check: n - k = 5 - 5 = 0 (still ≥ 0, continue)
    • Subtract k from n: n = 0
    • Increment k: k = 6
  11. Sixth iteration:
    • k = 6
    • Check: n - k = 0 - 6 = -6 (less than 0, exit loop)

Step 3: Return Value

Since we exit the loop when n - k < 0, the last fully completed row was k - 1 = 6 - 1 = 5.

Final Output: The function returns 5, meaning 5 complete rows of coins can be formed. ✅

Steps to write code

Step 1: Initialization

  • Define the function arrangeCoins with an integer parameter n.
  • Initialize k = 1 to represent the first row.

Step 2: Loop Until n Becomes Insufficient

  • Use a while loop with the condition n - k >= 0.
  • Inside the loop:
    • Subtract k from n.
    • Increment k for the next row.

Step 3: Return the Last Completed Row

  • The loop exits when n - k < 0, meaning the last fully completed row was k - 1.
  • Return k - 1.
Arranging Coins leetcode solution in all languages
Arranging Coins solution in C++ 
class Solution {
public:
    int arrangeCoins(int n) {
        int k = 1;
        
        // Deduct coins for each row until not enough coins remain
        while (n - k >= 0) {
			// Use up k coins for the current row
            n -= k;  
			// Move to the next row
            k++;     
        }
        
        // Return the number of fully completed rows
        return k - 1;
    }
};

Arranging Coins solution in java 
class Solution {
    public int arrangeCoins(int n) {
        int k = 1;
        
        // Deduct coins for each row until not enough coins remain
        while (n - k >= 0) {
            // Use up k coins for the current row
            n -= k;  
            // Move to the next row
            k++;     
        }
        
        // Return the number of fully completed rows
        return k - 1;
    }
}

Arranging Coins solution in python 
class Solution:
    def arrangeCoins(self, n: int) -> int:
        k = 1
        # Deduct coins for each row until not enough coins remain
        while n - k >= 0:
            # Use up k coins for the current row
            n -= k  
            # Move to the next row
            k += 1  
        
        # Return the number of fully completed rows
        return k - 1

Arranging Coins solution in javascript 
/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    let k = 1;
    
    // Deduct coins for each row until not enough coins remain
    while (n - k >= 0) {
        // Use up k coins for the current row
        n -= k;  
        // Move to the next row
        k++;     
    }
    
    // Return the number of fully completed rows
    return k - 1;
};

Arranging Coins Complexity Analysis

Time Complexity: O(√n)

Step 1: Identifying the Loop Growth

  • The function uses a while loop that iterates while n - k >= 0.
  • The value of k starts at 1 and increments by 1 in each iteration (k = 1, 2, 3, ...).
  • The sum of the first m natural numbers is given by the formula: S=m(m+1)/2.​ The loop runs until S ≤ n, meaning: m(m+1)/2 <= n

Step 2: Solving for m

  • Approximating the equation: m2/2≈n
  • Solving for m: m2≈2n → m≈√2n
  • This means the loop runs approximately O(√n) times.

Step 3: Overall Time Complexity

  • The dominant factor in the function is the while loop, which runs for O(√n) iterations.
  • Each iteration involves constant-time operations (n -= k andk++).
  • Therefore, the overall time complexity of the function is: O(√n)

Space Complexity: O(1)

Auxiliary Space Complexity
Additional storage used to solve the problem,excluding input

  • The function uses only two integer variables:
    • k (to track the current row number)
    • n (modified during execution)
  • These variables consume O(1) auxiliary space since their usage does not depend on n.

Total Space Complexity
Overall total storage used by the code includes input storage

  • The input is a single integer n. O(1)
  • There are no additional data structures (arrays, lists, recursion stack) used in the function.
  • Since the function only uses a constant amount of extra memory, the total space complexity is also O(1).

Final Space Complexity Breakdown

  • Auxiliary Space Complexity: O(1) (only a few integer variables are used)
  • Total Space Complexity: O(1) (no extra memory is allocated based on n)

Is the brute force approach efficient?

The brute force approach has a time complexity of O(√n). Given that nnn can be as large as 231−1, the maximum number of operations performed would be approximately √2147483647, which is 46341 operations at most.

This is well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.

In such environments, it is common for problems to handle up to 10⁶ operations within these limits.

Most competitive programming platforms, like LeetCode, allow up to 10⁶ operations per test case, meaning your solution should be able to handle this number of operations within the time limits.

Let's see if we can optimize the Arranging Coins leetcode solution.

Optimal Approach

Intuition:

To make our Arranging Coins solution better, let's think about all the useful details we can get from the fact that the ith row needs exactly iii coins.

Since each row needs a certain number of coins equal to its row number, the total number of coins used keeps increasing as we add more rows.

For example:

  • The 1st row needs 1 coin.
  • The 2nd row needs 2 more coins (total = 3).
  • The 3rd row needs 3 more coins (total = 6).
  • The 4th row needs 4 more coins (total = 10).

This pattern continues, and the total number of coins needed for k rows follows this formula: Sk = k(k+1)/2

Since this total only increases as we add more rows, the search space is monotonic, meaning it moves in just one direction, increasing.

Since the number of coins required always increases as we add more rows, we know that the total number of rows we can form lies between 1 and n.

At the smallest possible case, if we have just 1 coin, we can only form 1 row, so the minimum value in our search space is 1.

At the largest possible case, when we have n coins, the maximum number of complete rows k that we can form will be such that: k(k+1)/2 <= n

This formula tells us that the number of coins required to form k rows increases rapidly. We can approximate the maximum value of k by solving the inequality for k.

Rearranging the equation: k(k+1) <= 2n

For large values of k, the term k(k+1) behaves roughly like k2, so: k2 <= 2n

Taking the square root of both sides: k <= √2n

Thus, the maximum value of k that satisfies this equation will be approximately around √n​. This means the number of rows we need to check is not as large as n, but rather scales with the square root of n.

So, our possible number of complete rows lies in the range 1 to n.

To approach this efficiently, we can start by thinking of the range of possible rows from 1 to n, as we previously discussed. Instead of checking each row one by one, we can focus on finding the optimal row count by narrowing down the possibilities step by step. One way to do this is by taking the middle element of our range and examining it.

Let’s say we start with the range 1 to n and choose the middle value, let's call it mid. For each mid, we can calculate the total number of coins required to form mid rows using the formula: tot = mid (mid+1)/2

Now, depending on the value of tot, we can decide what to do next:

Case 1: mid × (mid + 1) / 2 < n

If the total number of coins required for mid rows is less than or equal to n, this means we can potentially form more rows. The search space can be narrowed down to the upper half of the current range, meaning we can now focus on values greater than mid (i.e., the range from mid + 1 to n). We know we can still fit more rows, so we adjust our range to explore the higher possibilities.

Illustration of Case 1 of Optimal Approach

Example:

Now, let’s say n = 7 coins. If we calculate mid = 3, the total number of coins required for 2 rows is: S2=3(3+1)/2=6

Since 6 coins are fewer than 7 coins, we know that we can potentially form more rows. So, we adjust our search to look at the upper half, which means the number of rows will be in the range 4 to 6.

Case 2: mid × (mid + 1) / 2 > n

On the other hand, if the total number of coins required for mid rows exceeds n, this means mid is too large, and we cannot form mid rows. Therefore, we reduce the search space to the lower half, focusing on values smaller than mid (i.e., the range from 1 to mid-1). We know that the solution must be in this smaller range because mid exceeds the total coins available.

Illustration of Case 2 of Optimal Approach

Example:

Let’s take n = 10 coins. We calculate the middle value mid = 5, and check the total number of coins needed for 5 rows: S5 = 5(5+1)/2=15

Since 15 coins exceed the available 10 coins, we cannot form 5 rows. Therefore, we know that the number of rows must be smaller than 5. We now adjust our search to focus on the lower half of the search space and look for the number of rows in the range 1 to 4.

Case 3: mid × (mid + 1) / 2 == n

In this case, the number of coins required for mid rows is exactly equal to n. This means that mid is the perfect number of complete rows we can form. We can directly return mid as the solution since the total number of coins perfectly fits the rows.

Illustration of Case 3 of Optimal Approach

Example:

Now, let’s say n = 6 coins. If we calculate mid = 3, the total number of coins required for 2 rows is: S2=3(3+1)/2=6

Since the total number of coins required for 3 rows is exactly equal to 6, we know that we can perfectly form 3 rows. So, we can directly return 3 as the answer, and there's no need for further searching.

In each of these cases, depending on the result of mid × (mid + 1), we adjust our search space either to the left or the right, narrowing it down efficiently.

Arranging Coins Algorithm

We start by defining the search space with two variables: low and high. Initially, low is set to 1, and high is set to n. These variables represent the range of possible row counts.

Next, we choose the middle element, mid, of the current search space, which is calculated as: mid = (low+high)/2

Then, we calculate the total number of coins required to form mid rows using the formula: tot=mid×(mid+1)/2

Once we have this value, we compare it to n (the total number of coins we have):

  • If tot is equal to n, then we have found the exact number of rows, and we can return mid immediately because this is the correct answer.
  • If tot​ is less than n, this means we can potentially form more rows. In this case, we adjust our search space by moving the low pointer to mid + 1 and continue searching for a larger number of rows.
  • If tot​ is greater than n, this means mid rows require more coins than are available. So, we shift the high pointer to mid - 1 to explore smaller values of mid.

We repeat this process of adjusting low and high until we narrow down the search to the correct number of rows. If at any point, S_mid is exactly equal to n, we can directly return mid as the answer because we have found the perfect number of rows.

However, if tot never exactly equals n, it means the last row will be incomplete. In this case, the value at low will give us the number of complete rows that can be formed. This is because, after narrowing down the search space, low will point to the maximum number of rows that can be fully completed with the available coins.

By using binary search, we efficiently reduce the range of possibilities and avoid having to check every single row count, significantly improving the performance compared to a brute-force solution.

Learn more about binary search here....

💡
Binary Search!
0:00
/0:57

Video Illustration of How Optimal Approach Works

Arranging Coins example

Step 1: Initialization

  • n = 15
  • low = 1
  • high = 15

Step 2: Iterations (Binary Search Process)

First Iteration:

  • Compute mid = (1 + (15 - 1) / 2) = (1 + 7) = 8
  • Compute tot = (8 * (8 + 1)) / 2 = (8 * 9) / 2 = 36
  • Since tot > n (36 > 15), update high = mid - 1 = 7.

Second Iteration:

  • Compute mid = (1 + (7 - 1) / 2) = (1 + 3) = 4
  • Compute tot = (4 * (4 + 1)) / 2 = (4 * 5) / 2 = 10
  • Since tot < n (10 < 15), update low = mid + 1 = 5.

Third Iteration:

  • Compute mid = (5 + (7 - 5) / 2) = (5 + 1) = 6
  • Compute tot = (6 * (6 + 1)) / 2 = (6 * 7) / 2 = 21
  • Since tot > n (21 > 15), update high = mid - 1 = 5.

Fourth Iteration:

  • Compute mid = (5 + (5 - 5) / 2) = 5
  • Compute tot = (5 * (5 + 1)) / 2 = (5 * 6) / 2 = 15
  • Since tot == n (15 == 15), return mid = 5.

Final Output

The function returns 5, meaning 5 complete rows of coins can be formed.

Steps to write code

Step 1: Initialization

  • Initialize two variables:
    • low = 1 (representing the smallest possible number of rows)
    • high = n (representing the maximum possible number of rows)

Step 2: Binary Search Loop

  • While low <= high:
    • Calculate mid = low + (high - low) / 2 to avoid overflow.
    • Compute the total number of coins needed to form mid complete rows: total=mid×(mid+1)/2​
    • If total == n, return mid because we can perfectly fill n coins with mid rows.
    • If total > n, set high = mid - 1 to check fewer rows.
    • If total < n, set low = mid + 1 to check for more rows.

Step 3: Final Return

  • After the loop ends, return high, which will represent the maximum number of complete rows that can be formed with n coins. This is because the loop terminates when the total exceeds n, and high holds the last valid value.
Arranging coins leetcode answer in all languages
Arranging Coins solution in C++ 
class Solution {
public:
    int arrangeCoins(int n) {
        // Initialize the search space between 1 and n
        int low = 1, high = n;
        
        // Perform binary search to find the largest k such that k*(k+1)/2 ≤ n
        while (low <= high) {
            // Compute the middle value of the search space
            int mid = (low + (high - low) / 2);
            
            // Calculate the total number of coins needed for mid rows
            long tot = (long) mid * (mid + 1) / 2;
            
            // If the total exactly matches n, mid is the answer
            if (tot == n) {
                return mid;
            }
            // If the total exceeds n, reduce the search space
            else if (tot > n) {
                high = mid - 1;
            }
            // If the total is less than n, increase the search space
            else {
                low = mid + 1;
            }
        }
        
        // Return the highest valid row count
        return high;
    }
};

Arranging Coins solution in java 
class Solution {
    public int arrangeCoins(int n) {
        // Initialize the search space between 1 and n
        int low = 1, high = n;
        
        // Perform binary search to find the largest k such that k*(k+1)/2 ≤ n
        while (low <= high) {
            // Compute the middle value of the search space
            int mid = low + (high - low) / 2;
            
            // Calculate the total number of coins needed for mid rows
            long tot = (long) mid * (mid + 1) / 2;
            
            // If the total exactly matches n, mid is the answer
            if (tot == n) {
                return mid;
            }
            // If the total exceeds n, reduce the search space
            else if (tot > n) {
                high = mid - 1;
            }
            // If the total is less than n, increase the search space
            else {
                low = mid + 1;
            }
        }
        
        // Return the highest valid row count
        return high;
    }
}

Arranging Coins solution in python 
class Solution:
    def arrangeCoins(self, n: int) -> int:
        # Initialize the search space between 1 and n
        low, high = 1, n
        
        # Perform binary search to find the largest k such that k*(k+1)/2 ≤ n
        while low <= high:
            # Compute the middle value of the search space
            mid = low + (high - low) // 2
            
            # Calculate the total number of coins needed for mid rows
            tot = mid * (mid + 1) // 2
            
            # If the total exactly matches n, mid is the answer
            if tot == n:
                return mid
            # If the total exceeds n, reduce the search space
            elif tot > n:
                high = mid - 1
            # If the total is less than n, increase the search space
            else:
                low = mid + 1
        
        # Return the highest valid row count
        return high

Arranging Coins solution in javascript 
/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    // Initialize the search space between 1 and n
    let low = 1, high = n;
    
    // Perform binary search to find the largest k such that k*(k+1)/2 ≤ n
    while (low <= high) {
        // Compute the middle value of the search space
        let mid = Math.floor(low + (high - low) / 2);
        
        // Calculate the total number of coins needed for mid rows
        let tot = (mid * (mid + 1)) / 2;
        
        // If the total exactly matches n, mid is the answer
        if (tot === n) {
            return mid;
        }
        // If the total exceeds n, reduce the search space
        else if (tot > n) {
            high = mid - 1;
        }
        // If the total is less than n, increase the search space
        else {
            low = mid + 1;
        }
    }
    
    // Return the highest valid row count
    return high;
};

Arranging Coins Complexity Analysis

Time Complexity: O(log n)

Step 1: Identifying the Search Space

  • The algorithm uses binary search on possible row numbers k, where k ranges from 1 to n.
  • Each iteration of binary search calculates mid and checks the sum formula: tot=mid×(mid+1)/2​
  • If tot == n, we return mid.
  • If tot > n, we move high = mid - 1.
  • If tot < n, we move low = mid + 1.

Step 2: Number of Iterations

  • Binary search reduces the search space by half in each iteration.

Breaking It Down

  1. At the beginning: The search space has n elements.
  2. After 1st iteration: The search space is reduced to n/2.
  3. After 2nd iteration: The search space is n/4.
  4. After k iterations: The search space becomes n / 2k.

The search ends when only one element remains, which happens when: n/2k = 1

Taking log base 2 on both sides: k=log⁡2(n)

Thus, binary search runs in O(log n) time complexity.

Step 3: Per Iteration Complexity

  • Constant-time operations: computing mid, calculating tot using the formula, and updating low or high.
  • Since all operations inside the loop take O(1) time, the total complexity remains O(log n).

Final Time Complexity

O(log n), as the algorithm efficiently finds the answer using binary search.

Space Complexity: O(1)

Auxiliary Space Complexity
The storage used to solve the problem excludes input storage

  • The function uses only a few integer variables: low, high, mid, tot (stored as long to prevent overflow)
  • These variables do not depend on n, meaning they require only O(1) auxiliary space.

Total Space Complexity
The total over storage used by the code includes input storage.

  • The function does not use any additional data structures (arrays, recursion stack, etc.).
  • Since all computations are done in-place with a constant number of variables, the total space complexity is also O(1).

Final Space Complexity Breakdown

Auxiliary Space Complexity: O(1) (only a few integer variables)
Total Space Complexity: O(1) (no additional memory usage based on n)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Water and Jug Problem

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

  • Fill either jug completely with water.
  • Completely empty either jug.
  • Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

2. Pyramid Transition Matrix

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains one less block than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific triangular patterns that are allowed. A triangular pattern consists of a single block stacked on top of two blocks. The patterns are given as a list of three-letter strings allowed, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.

  • For example, "ABC" represents a triangular pattern with a 'C' block stacked on top of an 'A' (left) and 'B' (right) block. Note that this is different from "BAC" where 'B' is on the left bottom and 'A' is on the right bottom.

You start with a bottom row of blocks bottom, given as a single string, that you must use as the base of the pyramid.

Given bottom and allowed, return true if you can build the pyramid all the way to the top such that every triangular pattern in the pyramid is in allowed, or false otherwise.