Sponsored
Sponsored
This approach involves sequentially counting how many coins are required to form a complete row one row at a time. While the number of available coins is greater than or equal to coins needed for the next row, continue adding rows and reducing the count of available coins accordingly.
Time Complexity: O(√n), as the sum of the first k natural numbers grows quadratically.
Space Complexity: O(1), constant space is used.
1#include <iostream>
2using namespace std;
3
4int arrangeCoins(int n) {
5 int k = 0;
6 while (n >= k + 1) {
7 k++;
8 n -= k;
9 }
10 return k;
11}
12
13int main() {
14 int n = 8;
15 cout << arrangeCoins(n) << endl; // Output: 3
16 return 0;
17}The same greedy logic is implemented in C++. The while loop efficiently counts complete rows by deducting the required coins for each row successively, with k representing the number of those complete rows.
Using a binary search, optimize the process of finding the maximum k where the sum of the first k natural numbers is less than or equal to n. Calculate mid values and determine if they result in a possible sum being less or equal to n and adjust the search space accordingly.
Time Complexity: O(log n)
Space Complexity: O(1)
1using System;
2
public class Solution {
public int ArrangeCoins(int n) {
long left = 0, right = n;
while (left <= right) {
long mid = left + (right - left) / 2;
long current = mid * (mid + 1) / 2;
if (current == n) return (int)mid;
if (current > n) right = mid - 1;
else left = mid + 1;
}
return (int)right;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int n = 8;
Console.WriteLine(solution.ArrangeCoins(n)); // Output: 3
}
}C# implementation uses a binary search to find the largest integer k such that the k-th triangular number does not exceed n, with careful integer handling to prevent overflow.