Coding interview Essentials

7. String to Integer

String to Integer

Introduction

The problem discussed in this chapter is an extremely popular one often used as a warm-up question asked during the onsite interview as well as part of many online assessment exercices. It is important to ask the right questions to the interview so to make sure that the problem is understood well and that all the corner cases are handled properly. For instance the interviewer might ask to take car care of negative numbers, but that might not be explicitly stated in the problem statement.

Problem statement

Write a function that given a string \(s\) containing only numbers (characters from the range [0-9]), parse it into its integer representation without using any library specific functions (like atoi() in C++ or Integer.parseInt() in Java).


If \(s\) ="12345", then the function should return the integer \(12345\).

Clarification Questions

Does the function need to handle integer overflow?

No, the input will never cause overflow.

Can the string have leading zeros?

Yes, the string might have one or more leading zeros.


If \(s\) ="0000012345", then the function should return the integer \(12345\).

Discussion

This problem can be solved very eleganlty by just using the idea behind the decimal positional numeral systems. In any positional number system, the ultimate numeric value of a digit is determined by the position it holds, not only by the digit itself. Take as an example the number \(427\): although \(7\) is thought of as a larger number than 4, the \(7\) is worth less than the \(4\) in this instance because of its respective position within the number. The value of a digit \(d\) at position \(i\) is equal to \(d\times 10^i\). Thus the value of the a number \(n=d_0d_1 \ldots d_k\) is equal to \((d_0 \times 10^0) + (d_1 \times 10^1) + \ldots + (d_k \times 10^k)\). Using this approach leading zeros are not a problem because they clearly do not contribute to the final result as \(0 \times 10^x = 0\).


\(n\) ="22498" then its decimal value is equal to: \((2 \times 10^4) + (2 \times 10^3) + (4 \times 10^2) + (9 \times 10^1) + (8 \times 10^0) = 20000 + 2000 + 400 +90 +8 = 22498\)

The idea above can be implemented by looping though the string from right to left and summing up each digit of the string at position \(i\) multiplied by \(10^i\) as shown in Listing [list:string_to_int1].

Listing 1: C++ solution to the string to integer problem.

int string_to_int1(const std::string &s)
{
  int ans = 0;
  int p   = 1;  // 10^i
  for (int i = s.size() - 1; i >= 0; i--)
  {
    const int char_to_int = (int)(s[i] - '0');
    ans += char_to_int * p;
    p *= 10;
  }
  return ans;
}

This is considered a good solution, as its complexity is linear in the size of the input string and handles leading zeros elegantly.

Common Variation

  • Add support for negative numbers. One optional char which could either be + or -, at the beginning of the string signals the sign. See Listing [list:string_to_int_negative].

  • Return \(0\) when the answer does not fit into an int.

  • Raise an exception (or return a certain value) in case of bad input. For instance when letters are present in the string e.g. \(s=123f456\).

Listing 2: C++ solution to the string to integer problem with negative number support.

int string_to_int_negative(const std::string &s)
{
  if (s.size() == 0)
    return 0;
  const int sign = s[0] == '-' ? -1 : 1;
  // skip the first char if sign is specified
  const int start = (s[0] == '-') || (s[0] == '+') ? 1 : 0;
  return sign * string_to_int1(std::string(begin(s) + start, end(s)));
}