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


  • 40
    R

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



  • 2
    W

    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)


  • 1
    V

    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.


  • 5
    R

    @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!


  • 0
    V

    @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


  • 0
    R

    Golang version of square root solution:

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

  • 2
    J

    @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

  • 0
    V

    @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?


  • 0

  • 0
    F
    This post is deleted!

  • 0

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


  • 0
    B

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


  • 0
    E

    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.


  • 0

    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;
        }
    

  • 0
    C

    @Evilgit said in [JAVA] Clean Code with Explanations and Running Time [2 Solutions]:

    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


  • 0

    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;
        }
    

  • 0
    M

    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.


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

  • 0
    D

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


Log in to reply
 

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