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 <stdio.h>
2
3int arrangeCoins(int n) {
4 int k = 0;
5 while (n >= k + 1) {
6 k++;
7 n -= k;
8 }
9 return k;
10}
11
12int main() {
13 int n = 5;
14 printf("%d\n", arrangeCoins(n)); // Output: 2
15 return 0;
16}The solution involves a while loop that continues to subtract sequential numbers from n. Each time a subtraction is successful, the count of complete rows (k) is incremented. The loop terminates when n is less than the number of coins needed for the next row.
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)
1class
This Java solution applies a binary search over possible values of k, effectively pinpointing the maximum k such that the triangular number for k is less than or equal to n, using long to avoid overflow issues.