Arranging Coins

                                            
class Solution {
public:
    int arrangeCoins(int n) {
        long left = 0, right = n;
        long k, curr;
        while (left <= right) {
            k = left + (right - left) / 2;
            curr = k * (k + 1) / 2;
            if (curr == n) {
                return k;
            }
            if (n < curr) {
                right = k - 1;
            } else {
                left = k + 1;
            }
        }
        return right;
    }
};

                                            
class Solution {
    public int arrangeCoins(int n) {
        return (int) (Math.sqrt(2.0 * n + 0.25) - 0.5);
    }
}

                                            
class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left <= right:
            k = (left + right) // 2
            curr = k * (k + 1) // 2
            if curr == n:
                return k
            elif curr < n:
                left = k + 1
            else:
                right = k - 1
        return right

                                            
int arrangeCoins(int n) {
    long left = 1, right = n;
    long curr, k;
    
    while (left <= right) {
        k = left + (right - left) / 2; // Binary search
        curr = k * (k + 1) / 2;
        
        if (curr == n) {
            return k;
        }
        
        if (n < curr) {
            right = k - 1;
        } else {
            left = k + 1;
        }
    }
    
    return right;
}

                                            
public class Solution {
    public int ArrangeCoins(int n) {
        return (int)(Math.Sqrt(2 * (long)n + 0.25) - 0.5);
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    return Math.floor(Math.sqrt(2 * n + 0.25) - 0.5);
};

                                            
function arrangeCoins(n: number): number {
    let left = 0;
    let right = n;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        const curr = mid * (mid + 1) / 2;
        
        if (curr === n) {
            return mid;
        } else if (curr < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return right;
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function arrangeCoins($n) {
        return floor(sqrt(2 * $n + 0.25) - 0.5);
    }
}

                                            
class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var left = 0
        var right = n
        while left <= right {
            let mid = left + (right - left) / 2
            let sum = mid * (mid + 1) / 2
            if sum == n {
                return mid
            } else if sum < n {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return right
    }
}

                                            
class Solution {
    fun arrangeCoins(n: Int): Int {
        var left = 1
        var right = n
        while (left <= right) {
            val mid = left + (right - left) / 2
            val curr = mid.toLong() * (mid + 1) / 2
            if (curr == n.toLong()) {
                return mid
            } else if (curr < n.toLong()) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return right
    }
}

                                            
class Solution {
  int arrangeCoins(int n) {
    int left = 0;
    int right = n;
    
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      int curr = mid * (mid + 1) ~/ 2;
      
      if (curr == n) return mid;
      if (curr < n) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return right;
  }
}

                                            
func arrangeCoins(n int) int {
    return int((-1 + math.Sqrt(1+8*float64(n))) / 2)
}

                                            
# @param {Integer} n
# @return {Integer}
def arrange_coins(n)
    ((-1 + Math.sqrt(1 + 8 * n)) / 2).to_i
end

                                            
-spec arrange_coins(N :: integer()) -> integer().
arrange_coins(N) ->
    Rows = trunc((math:sqrt(1 + 8*N) - 1) / 2),
    Rows.

                                            
defmodule Solution do
  @spec arrange_coins(n :: integer) :: integer
  def arrange_coins(n) do
    floor((-1.0 + :math.sqrt(1 + 8 * n)) / 2)
  end
end

To solve this coding challenge, it is essential to understand the problem requirements and derive an efficient method to find the number of complete rows that can be formed using a given number of coins

n

# Explanation

The problem is to determine how many complete rows can be formed to build a staircase with a given number of coins \( n \). In this staircase:

The 1st row has 1 coin,
The 2nd row has 2 coins,
The 3rd row has 3 coins,
and so forth, such that the \( i \)-th row has \( i \) coins.

Given this, if \( n \) is the total number of coins available, we need to find the maximum integer \( k \) such that the sum of the first \( k \) integers (coinciding with the number of coins in the first \( k \) rows) is less than or equal to \( n \). The sum of the first \( k \) integers is given by the formula \( \frac{k \cdot (k + 1)}{2} \).

# Strategy

To find the value of \( k \) efficiently, we can use a binary search approach because the problem inherently involves finding a boundary within a sorted range of numbers.

Initialize Left and Right Pointers :

These pointers (
left

and
right

) will help to conduct a binary search within the range
[1, n]

because the maximum possible rows cannot exceed \( n \) itself (e.g., in the worst-case scenario where each row has only one coin).

Binary Search Execution :

Calculate the middle point (
mid

) in the current range.
Compute the total number of coins required to form
mid

rows using the formula \( \frac{mid \cdot (mid + 1)}{2} \).
Compare this computed value with
n

:

If the computed value is equal to
n

,
mid

is the maximum number of complete rows, and the search ends.
If the computed value is less than
n

, it means we can form more rows, so move the left pointer up (
left = mid + 1

).
If the computed value is more than
n

, it means we need fewer rows, so move the right pointer down (
right = mid - 1

).

Conclusion of Search :

The search stops when the
left

pointer exceeds the
right

pointer. At this point, the
right

pointer will point to the maximum number of complete rows that can be formed.

# Detailed Steps in Pseudocode

                                            
FUNCTION arrangeCoins(n):
# Initialize the left and right pointers 
left <- 1
right <- n

# Execute the binary search loop 
WHILE left <= right:
# Calculate the middle point
mid <- (left + right) / 2

# Calculate the total number of coins needed for `mid` rows
currentCoins <- mid * (mid + 1) / 2 

# Check if computed number of coins meets the criteria
IF currentCoins == n:
RETURN mid
ELSE IF currentCoins < n:
# If less coins are used, check the higher half
left <- mid + 1
ELSE:
# If more coins are used, check the lower half
right <- mid - 1

# Return the maximum number of complete rows
RETURN right

# Step-by-Step Explanation (Detailed Steps in Pseudocode)

Initialize two pointers,
left

to 1 and
right

to
n

. These pointers will help us to narrow down the possible number of complete rows using a binary search.
Enter a
while

loop which will execute as long as
left

is less than or equal to
right

.
Calculate the
mid

point in the current range. The
mid

point represents a candidate number of rows we'll test.
Compute the number of coins required to form
mid

rows. This is done using the formula for the sum of the first
mid

natural numbers: \( mid \times (mid + 1) / 2 \).
Compare this computed value (
currentCoins

) to
n

:

If
currentCoins

equals
n

, then
mid

is the exact number of complete rows, and we return
mid

.
If
currentCoins

is less than
n

, it implies fewer coins are used, so we shift our search to the higher half by setting
left

to
mid + 1

.
If
currentCoins

is greater than
n

, it suggests more coins are required than available, so we shift our search to the lower half by setting
right

to
mid - 1

.

Once the loop exits (i.e.,
left

exceeds
right

), the maximum number of complete rows that can be formed is pointed by
right

, which is then returned.

This pseudocode outlines an efficient approach to solve the given coding challenge using a binary search methodology, ensuring a logarithmic time complexity relative to the input size.