Vishal Kotcherlakota Vishal Kotcherlakota - 1 month ago 24
Java Question

Convert int to Hex String without using Integer.toHexString();

Before you downvote: This is a LeetCode question. Read the rules below and you'll understand why I'm not using any of the Java APIs that do this for me.

Following is the problem statement from
LeetCode.


Given an integer, write an algorithm to convert it to hexadecimal. For
negative integer, two’s complement method is used.

Note:


  • All letters in hexadecimal (a-f) must be in lowercase.

  • The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0';
    otherwise, the first character in the hexadecimal string will not be
    the zero character.

  • The given number is guaranteed to fit within the range of a 32-bit signed integer.

  • You must not use any method provided by the library which converts/formats the number to hex directly.




Here's my solution:

public class Solution {
private static final String characters = "0123456789abcdef";
private static final char[] digits = characters.toCharArray();

private Stack<Integer> stack = new Stack<>();
public String toHex(int num) {
if (num == 0) return "0";

stack.clear();
while (num != 0) {
stack.push(getDigit(num));
num = num >>> 4;
System.out.println(num);
if (stack.size() > 8) break;
}

StringBuilder buffer = new StringBuilder();
while (!stack.empty()) {
buffer.append(digits[stack.pop()]);
}

return buffer.toString();
}

private int getDigit(int num) {
int result = num & 0xF;
return result;
}
}


The problem is that this solution works, but it's not very performant--I'm in the bottom 1% of runtimes with this solution. I'm wondering if my use of the Stack Object or the StringBuilder is causing me grief.

enter image description here

It's also totally possible that a ton of submissions are ignoring the restriction and using the Java APIs anyway. :) But I figured I'd post here and learn how I could make this more efficient.

Answer

I managed a small improvement with just a few tweaks to your code.

enter image description here

I've shaved 8ms off the run time moving it up to beating 51.90% of the other solutions.

public class Solution {
    private static final char[] digits = "0123456789abcdef".toCharArray(); 

    private Stack<Integer> stack = new Stack<>();
    public String toHex(int num) {
        if (num == 0) return "0";

        stack.clear();
        while (num != 0) {
            stack.push(num & 0xF);
            num = num >>> 4;
            if (stack.size() > 8) break;
        }

        StringBuilder buffer = new StringBuilder();
        while (!stack.empty()) {
            buffer.append(digits[stack.pop()]);
        }

        return buffer.toString();
    }
}

Firstly, I changed the way the digits array is constructed, condensing the two original lines into one.

I also deleted the System.out.println call.

Finally, I replaced the call to the getDigit() method with its contents inlined in the main code.

* UPDATE *

This is also a cleaner option, reducing the number of loops to one and removing the need to use a Stack.

public class Solution {
    private static final char[] digits = "0123456789abcdef".toCharArray(); 

    public String toHex(int num) {
        if (num == 0) return "0";

        StringBuilder buffer = new StringBuilder();
        while (num != 0) {
            buffer.append(digits[num & 0xF]);
            num = num >>> 4;
        }
        return buffer.reverse().toString();
    }
}

enter image description here

Note: Performance of this seems to fluctuate between 7ms and 8ms.

Comments