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


  • 9
    R

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


    Full Solutions and Explanations

    Solution 1

    public class Solution {
        public String toHex(int num) {
            long n = num & 0x00000000ffffffffL;
            char[] map = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
            StringBuilder sb = new StringBuilder();
            while (n > 0) {
                sb.insert(0, map[(int) (n % 16)]);
                n = n / 16;
            }
            return num == 0 ? "0" : sb.toString();
        }
    }
    

    Complexity Analysis

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

    Time Complexity:

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

    Auxiliary Space:

    • Worst Case `O(log_b(n))` : With respect to the input, the algorithm will always depend on the size of input.

    Algorithm

    Approach: Divide and Modding

    To deal with negative number, the number is masked against long data type. This process will convert it to a positive long number. A simple while loop is then use to extract each base digit until number becomes `0`.

    For Integer.MAX_VALUE or Integer.MIN_VALUE or any input with 8 Hexadecimal characters where the iterations would last the longest. For Integer.MAX_VALUE the algorithm will run for at most `ceil(log_16 (2^31 - 1) + 1) = 8` times.


    Solution 2

    public class Solution {
        public String toHex(int num) {
            if (num == 0) return "0";
            char[] map = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
            StringBuilder sb = new StringBuilder();
            while (num != 0) {
                sb.insert(0, map[num & 0b1111]);
                num = num >>> 4;
            }
            return sb.toString();
        }
    }
    

    Complexity Analysis

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

    Time Complexity:

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

    Auxiliary Space:

    • Worst Case `O(log_b(n))` : With respect to the input, the algorithm will always depend on the size of input.

    Algorithm

    Approach: Shifting and Masking

    Number is masked against binary of 1111 each time to get the component value which is then mapped to corresponding character. >>> is used to right-shifted `4` bit positions with zero-extension. The zero-extension will naturally deal with negative number.

    StringBuilder is used due to its efficiently in inserting character to existing StringBuilder object. If normal String is used then each insertion by + operation will have to copy over the immutable String object which is highly inefficient.

    For Integer.MAX_VALUE or Integer.MIN_VALUE or any input with 8 Hexadecimal characters where the iterations would last the longest. For Integer.MAX_VALUE the algorithm will run for at most `ceil(log_16 (2^31 - 1) + 1) = 8` times.



  • 0
    T
    This post is deleted!

  • 0
    W

    Hi,
    I understand you convert a signed integer to an unsigned long , but why are the hex form of these two the same?


Log in to reply
 

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