### [JAVA] Clean Code with Explanations and Running Time [2 Solutions]

Full Solutions and Explanations

**Solution 1**

```
public class Solution {
public int arrangeCoins(int n) {
int start = 0;
int end = n;
int mid = 0;
while (start <= end){
mid = (start + end) >>> 1;
if ((0.5 * mid * mid + 0.5 * mid ) <= n){
start = mid + 1;
}else{
end = mid - 1;
}
}
return start - 1;
}
}
```

#### Complexity Analysis

Uniform cost model is used as Cost Model and `n` is the input number. `b` in this case would be `2`.

**Time Complexity:**

- Best Case `O(log_b(n))` : With respect to the input, the algorithm will always depend on the value of input.
- Average Case `O(log_b(n))` : With respect to the input, the algorithm will always depend on the value of input.
- Worst Case `O(log_b(n))` : With respect to the input, the algorithm will always depend on the value of input.

**Auxiliary Space:**

- Worst Case `O(1)` : Additional variables are of constant size.

#### Algorithm

**Approach:** Binary Search

The problem is basically asking the maximum length of consecutive number that has the running sum lesser or equal to `n`. In other word, find `x` that satisfy the following condition:

Running sum can be simplified,

Binary search is used in this case to slowly narrow down the `x` that will satisfy the equation. Note that `0.5 * mid * mid + 0.5 * mid`

does not have overflow issue as the intermediate result is implicitly autoboxed to `double`

data type.

**Solution 2**

```
public class Solution {
public int arrangeCoins(int n) {
return (int) ((Math.sqrt(1 + 8.0 * n) - 1) / 2);
}
}
```

#### Complexity Analysis

Uniform cost model is used as Cost Model and `n` is the input number. `b` in this case would be `2`.

**Time Complexity:**

- Best Case `O(1)` : With respect to the input, the algorithm will always perform basic mathematical operation that run in constant time.
- Average Case `O(1)` : With respect to the input, the algorithm will always perform basic mathematical operation that run in constant time.
- Worst Case `O(1)` : With respect to the input, the algorithm will always perform basic mathematical operation that run in constant time.

**Auxiliary Space:**

- Worst Case `O(1)` : No extra space is used.

#### Algorithm

**Approach:** Mathematics

The problem is basically asking the maximum length of consecutive number that has the running sum lesser or equal to `n`. In other word, find `x` that satisfy the following condition:

Running sum can be simplified,

Using quadratic formula, `x` is evaluated to be,

Negative root is ignored and positive root is used instead. Note that `8.0 * n`

is very important because it will cause Java to implicitly autoboxed the intermediate result into `double`

data type. The code will not work if it is simply `8 * n`

. Alternatively, an explicit casting can be done `8 * (long) n)`

.