9
\$\begingroup\$

I am studying about the converting int to string and string to int without using toString and parseInt method. I already made methods. However, I don't believe that my way of doing was the best. I would like to improve these function.

For example, the first converts from String to int:

public static int StringToint(String number)
        int eachnumber = 0;
    int intConvert = 48;
    int reVal = 0;
    int index;
    int maxlen =number.length() - 1;
        for(index = 0 ; index <= maxlen ; index++)
    {
        eachnumber = number.charAt(index);

        eachnumber = eachnumber  - intConvert;

        reVal = reVal + (eachnumber * (int) Math.pow(10, maxlen - index));
    }
    return reVal;
}

Second, for converting int to String:

public static String IntToString(int number)
{
    int StringConvet = 48;

    int eachDigit = number;
    int afterDivide = number;
    String reVal = "";

    while(afterDivide >0)
    {
        eachDigit = afterDivide % 10;
        afterDivide = afterDivide / 10;
        if(eachDigit == 0)
        {
            reVal += "0";
        }
        else if(eachDigit == 1)
        {
            reVal += "1";
        }
        else if(eachDigit == 2)
        {
            reVal += "2";
        }
        else if(eachDigit == 3)
        {
            reVal += "3";
        }
        else if(eachDigit == 4)
        {
            reVal += "4";
        }
        else if(eachDigit == 5)
        {
            reVal += "5";
        }
        else if(eachDigit == 6)
        {
            reVal += "6";
        }
        else if(eachDigit == 7)
        {
            reVal += "7";
        }
        else if(eachDigit == 8)
        {
            reVal += "8";
        }
        else if(eachDigit == 9)
        {
            reVal += "9";
        }
    }
    String reVal2 = "";
    for(int index =  reVal.length() -1 ; index >= 0 ; index--)
    {
        reVal2 += reVal.charAt(index);
    }
    return reVal2;
}

I am sure that the StringToint method is \$O(n)\$ and intToString method will be \$O(n^2)\$. However, I am really sure that there are ways to improve these two methods. Is there any way to improve these two functions?

\$\endgroup\$
  • \$\begingroup\$ Your making these on purpose right.. Instead of just using Integer.parseInt() and Integer.toString().. \$\endgroup\$ – barsju Mar 26 '12 at 21:35
  • \$\begingroup\$ yep, I am studying about interview questions and I just want to know the better way to build these methods. \$\endgroup\$ – Dc Redwing Mar 26 '12 at 21:41
  • \$\begingroup\$ What happens if you need a string representation of a negative number? \$\endgroup\$ – Clockwork-Muse Apr 4 '12 at 21:56
  • \$\begingroup\$ For the love of baby Jesus, fix your indentation! \$\endgroup\$ – Emily L. Jul 14 '15 at 15:18
12
\$\begingroup\$

To improve your intToString() method you should consider using a StringBuilder, and specifically the method StringBuilder.append(int).

Iterate digits in your int, and for each digit you can append(eachDigit) to the StringBuilder element. This will also reduce the complexity of intToString() to \$O(n)\$ since you do not need to create a new String instance each iteration. To get a String object from the StringBuilder, use StringBuilder.toString(). Or, if you are not allowed, you can use StringBuilder.subString(0).

You should also use a StringBuilder.append() (using the same idea) to reverse the resulting string (your second loop in your code).

Since it is not homework (as per comments), I have no problems providing a code snap. It should look something like this:

public static String intToString(int n) { 
    if (n == 0) return "0";
    StringBuilder sb = new StringBuilder();
    while (n > 0) { 
        int curr = n % 10;
        n = n/10;
        sb.append(curr);
    }
    String s = sb.substring(0);
    sb = new StringBuilder();
    for (int i = s.length() -1; i >= 0; i--) { 
        sb.append(s.charAt(i));
    }
    return sb.substring(0);
}

Notes:

  • You can also use StringBuilder.reverse() instead of the second loop.
  • In here, \$O(n)\$ means linear in the the number of digits in the input number (n is the number of digits in the input number - not the number itself!) If you are looking for the complexity in terms of the initial number (it is \$O(\log(n))\$) since you divide your element by 10 each iterations, you have a total of \$\log_{10}(\text{number})\$ iterations for each loop, which results in \$O(\log(\text{number}))\$.
\$\endgroup\$
  • \$\begingroup\$ sorry , it is not homework. It actually came from the interview questions. I was preparing the interview for coding questions. Anyway, thanks a lot :) \$\endgroup\$ – Dc Redwing Mar 26 '12 at 21:42
  • \$\begingroup\$ This is still O(n^2) though, you can easily insert at beginning, otherwise there no need to use a StringBuilder (even because javac will optimize it to a StringBuilder in most cases) \$\endgroup\$ – Jack Mar 26 '12 at 21:54
  • \$\begingroup\$ @Jack: No, it is O(n) - each loop is O(n) - the algorithm is total of O(2 * n) = O(n). inserting element in the beginning will probably make it O(n^2) - since inserting an element to the beginning of dynamic array is O(n) each for each insert. \$\endgroup\$ – amit Mar 26 '12 at 21:58
  • \$\begingroup\$ Yes, yours it still O(2n), misread the code sorry. I was thinking about the internal implementation of StringBuilder, I thought it worked by doing some black magic with linked lists, not a plain internal array. But if it's a dynamic array of course insert will require O(n). I guess that with Math.ceil(Math.log10(number)) we could be able to avoid reversing the string then. \$\endgroup\$ – Jack Mar 26 '12 at 23:27
2
\$\begingroup\$

For your example , I should point out some problems : first , when you add two add string frequently, you should use StringBuilder instead ; second , you should consider Integer.MIN_VALUE into account!Here is my code:

public static String parseInt(int integer)
{
    boolean ifNegative = integer<0;
    boolean ifMin = integer == Integer.MIN_VALUE;
    StringBuilder builder = new StringBuilder();        
    integer = ifNegative?(ifMin?Integer.MAX_VALUE:-integer):integer;    
    List<Integer> list = new LinkedList<Integer>(); 
    int remaining = integer;
    int currentDigit = 0 ;

    while(true)
    {
        currentDigit = remaining%10;
        list.add(currentDigit);
        remaining /= 10;
        if(remaining==0) break;
    }

    currentDigit = list.remove(0);
    builder.append(ifMin?currentDigit+1:currentDigit);
    for(int c : list)
        builder.append(c);
    builder.reverse().insert(0, ifNegative?'-':'+');
    return builder.toString();
}
\$\endgroup\$
1
\$\begingroup\$

Your approach seems indeed quite overkill.

Conversion from string to int can be done in a way similar to yours, but by multiplying the result by 10 at every step, without the need to calculate the i-th power for every digit:

int stringToInt(String s)
{
  int r = 0;
  for (int i = 0; i < s.length(); ++i)
  {
    if (i > 0)
      r *= 10;

    r += s.charAt(i)-'0';
  }
  return r;
}

While conversion from int to string can take into account the difference between the char '0' and the current character of the string without the need of a if/else chain. In addition you can use a string buffer to insert characters at the beginning to avoid the necessity of reversing the string.

String intToString(int i)
{
  StringBuilder b = new StringBuilder();

  while (i != 0)
  {
    b.insert(0, (char)('0'+i%10));
    i /= 10;
  }

  return b.toString();
}

Mind that the cast to char is needed to avoid using the method insert(int offset, int value) that would actually convert the int to a string.

\$\endgroup\$
  • \$\begingroup\$ note that b.insert() is O(n). have a look on the performance of dynamic array [which I think this is how StringBuilder is implemented]. inserting an element to the beginning is O(n) each, so total of O(n^2). Also, there is a special case of i == 0, which should be handled. \$\endgroup\$ – amit Mar 26 '12 at 22:00