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

• ### [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:

`1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + x <= n`
`sum_{i=1}^x i <= n`

Running sum can be simplified,

`(x * ( x + 1)) / 2 <= n`

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:

`1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + x <= n`
`sum_{i=1}^x i <= n`

Running sum can be simplified,

`(x * ( x + 1)) / 2 <= n`

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

`x = 1 / 2 * (-sqrt(8 * n + 1)-1)` (Inapplicable) or `x = 1 / 2 * (sqrt(8 * n + 1)-1)`

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)`.

• Some info about that second algorithm and this problem. https://en.wikipedia.org/wiki/Triangular_number
There is a formula in here to test any number (the one they used)

• dude man love the soln.. great ideas and concepts. only one complaint. like y u gotta do the right bitshift by 1? r u just trying to be confusing haha, i mean i dont mean to be rude. but i think it would have been much clearer if you just divided by 2.

• @vikram4

``````mid = (start + end) / 2;
``````

will have overflow issue when start and end is very large. Imagine if `start` is `0.5MAX_INT` and `end` is `MAX_INT`. `start + end` will be potentially be `1.5MAX_INT` which is equivalent to `1011 1111 1111 1111 1111 1111 1111 1110` binary string.
Now if you just use `/2` then it will treat the binary string as signed integer `(-1073741826)` and you mid point will be negative. However, if you logical shift right (Logical right shift, however, does not care that the value could possibly represent a number; it simply moves everything to the right and fills in from the left with 0s) then it is equivalent to dividing by two without caring about the sign.

Alternatively to prevent overflow you can use this expression instead
`int mid = start + ((end - start) / 2)`
This will ensure no overflow problem exists.

The expression `mid = (start + end) / 2` is a quite well known binary search bug. You can read more about it here https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html.

I hope this makes things clearer!

• @ratchapong.t hey there, thanks for the detailed explanation. i think that's a fair and valid point. but i guess it's a java/c thing. for me using python, i beleive i automatically get a long int type if i need it, so i was able to just divide by 2 and not use any shifting. For anyone who is curious, I thought this was an interesting post:
http://stackoverflow.com/questions/2811319/difference-between-and

Basically, ratchapong is doing a logical instead of arithmetic right shift to cancel the sign extension when shifting.
Thanks for the article ratchapong, and yes it did make things clearer

• Golang version of square root solution:

``````import "math"

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

• @ratchapong.t
Thank you for sharing.
I wonder about 2 things that I need more explanation if possible:

1. start = mid + 1 OR start = mid
2. why return start-1

• @ratchapong-t

Hi, I've got a question regarding your first solution.

What's the reason behind mid = (start + end )/2
Why find mid? Why not do it with 'n' itself?

• This post is deleted!

• @VRAMJI Because going by `n` will be `O(n)`, and going by `mid` is `O(logn)`.

• @ratchapong.t If (0.5 * mid * mid + 0.5 * mid ) == n, why would you not just return 'mid' and reset start to 'mid + 1'?

• In the solutin 2, if I write

`````` return (int) ((Math.sqrt(1 + 8 * n) - 1) / 2);
``````

I will get a wrong anser, only

`````` return (int) ((Math.sqrt(1 + 8.0 * n) - 1) / 2);
``````

works.
I an wondering why.

• Thanks for sharing, especially the trick to avoid overflow. But maybe Long is more straightforward, right?

``````    public int arrangeCoins(int n) {
long l = 0, r = n, t = 2 * (long) n;
while (l < r) {
long m = (l + r + 1) / 2;
if ((1 + m) * m <= t) l = m;
else r = m - 1;
}
return (int) l;
}
``````

• In the solutin 2, if I write

`````` return (int) ((Math.sqrt(1 + 8 * n) - 1) / 2);
``````

I will get a wrong anser, only

`````` return (int) ((Math.sqrt(1 + 8.0 * n) - 1) / 2);
``````

works.
I an wondering why.

I think n*8 may be bigger than Max Integer value, n * 8.0 is float, so it's ok

j

• My intuitive solution:

``````    public int arrangeCoins(int n) {

int rowLen = 1, res = 0;
while(true){
n = n - rowLen;
if(n < 0) break;
res++;
rowLen++;
}
return res;
}
``````

• I'm curious as to why we are using ((0.5 * mid * mid + 0.5 * mid ) <= n) to check? I am checking with (mid(mid + 1)) / 2 > n then treating this as a first occurrence of bad version. I am using (mid(mid +1)) /2 Since we know that the sum of numbers up to n inclusive is the formula (n(n+1))/2.

• ``````public class Solution {
public int arrangeCoins(int n) {
int i=0;
while(n > 0){
i+=1;
n-=i;
}

return n==0 ? i : i-1;

}
}
``````

• @jun711 You can try google "binary search loop invariant proof". Loop invariant gives a convincing proof of the edge conditions

• @Evilgit overflow

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.