Problem

Implement two functions: intToString() and stringToInt().

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// intToString()
Input: 0
Output: "0"
Input: 123
Output: "123"
Input: -123
Output: "-123"
Input: -120
Output: "-120"

// stringToInt()
Input: "0"
Output: 0
Input: "123"
Output: 123
Input: "-123"
Output: -123
Input: "-120"
Output: -120

Analysis

intToString()

Also refer to 7. Reverse Integer.

Let’s first analyze the incorrect version. Here are two tiny errors in the following code.

The basic idea is to record the negative sign, sum up from LSD to MSD, and finally reverse the whole string.

1
2
3
4
5
6
7
8
9
10
11
12
13
public static String intToString(int x) {
  boolean isNegative = (x < 0);
  x = Math.abs(x);

  StringBuilder sb = new StringBuilder();
  while (x > 0) {
    int digit = x % 10;
    sb.append(digit);
    x /= 10;
  }

  return sb.append(isNegative ? "-" : "").reverse().toString();
}

Error #1:

When x == 0, the StringBuilder remains empty. Two solutions:

  • Use do-while.
  • Add if (x == 0) return 0; special case handler.
1
2
3
4
do {
  int digit = x % 10;
  sb.append(digit);
} while (x > 0);

Error #2:

  • Why can’t we do x = Math.abs(x) at the beginning?
  • Why should we use x != 0 rather than x > 0?

Consider the case when x = -2147483648, which is Integer.MIN_VALUE. If we extract the numeric part and process it as a positive number, it would overflows.

Solutions:

  • Do Math.abs inside while.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static String intToString(int x) {
      boolean isNegative = (x < 0);
      StringBuilder sb = new StringBuilder();
      do {
        int digit = Math.abs(x % 10);
        sb.append(digit);
        x /= 10;
      } while (x != 0);
      return sb.append(isNegative ? "-" : "").reverse().toString();
    }

  • Use a long integer to store x.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public static String intToString(int x) {
      long y = x;
      boolean isNegative = (y < 0);
      StringBuilder sb = new StringBuilder();
      y = Math.abs(y);
      do {
        long digit = y % 10;
        sb.append(digit);
        y /= 10;
      } while (y != 0);

      return sb.append(isNegative ? "-" : "").reverse().toString();
    }

Time: $O(N)$
Space: $O(1)$

stringToInt()

Assume the input is valid. It can be extended if s could be a very large number, then we should use long type.

1
2
s.replace("-", "");      // s will not change!
s = s.replace("-", "");  // we must update s

Remember String in Java is immutable.

1
2
3
4
5
6
7
8
9
10
11
12
// Assume the input is valid
public static int stringToInt(String s) {
  int sign = s.startsWith("-") ? -1 : +1;
  s = s.replace("-", ""); // remove the "-" (immutable!)
  // conversion (from MSD to LSD)
  int num = 0;
  for (int i = 0; i < s.length(); ++i) {
    int digit = s.charAt(i) - '0';
    num = num * 10 + digit;
  }
  return sign * num;
}

Time: $O(N)$
Space: $O(1)$