Home | Projects | Notes > Problem Solving > EPI - 7.1. Interconvert Strings and Integers

EPI - 7.1. Interconvert Strings and Integers

Solutions in C++

Solution 1

Negative numbers are handled by recording the sign and negating the result.

Complexity Analysis:

• $T=O(n)$$T = O(n)$, where $n$$n$ is the number of digits in the given integer

  In practice, $n$$n$ may be limited by whatever numeric data-types the language supports (e.g., int32_t, int64_t). But if arbitrary precision number types are used (which some languages, like Python, use by default) then there is no limit to the number of digits (other than available memory obviously).

• $S=O(1)$$S = O(1)$, since no additional memory space is used other than a string object to return

Solution:

23
1
#include <string>
2

3
using namespace std;
4

5
string IntToString(int x)
6
{
7
    bool is_negative = x < 0 ? true : false;
8
    string result;
9

10
    if (is_negative)
11
        x = -x;
12

13
    while (x)
14
    {
15
        result.insert(0, 1, (x % 10) + '0');
16
        x /= 10;
17
    }
18

19
    if (is_negative) 
20
        result.insert(0, 1, '-');
21

22
    return result;
23
}

Inserting a single character rather than a string:

• iterator insert(const_iterator p, char c);

  3
  1
  string s = "bc";
  2
  string::iterator it = s.begin();
  3
  s.insert(it, 'a');      // Insert 'a' to the position pointed to by the iterator 'it'
  

Inserting n consecutive copies of character c:

• string& insert(size_t pos, size_t n, char c);

  2
  1
  string s = "bc";
  2
  s.insert(0, 1, 'a');    // Insert 'a' to the position s.at(0) or s[0]
  

Instead of prepending digits to the string, you could apend them and reverse the string at the end using the reverse() algorithm.

24
1
#include <string>
2

3
using namespace std;
4

5
string IntToString(int x)
6
{
7
    bool is_negative = x < 0 ? true : false;
8
    string result;
9

10
    if (is_negative)
11
        x = -x;
12

13
    while (x)
14
    {
15
        result += x % 10 + '0';
16
        x /= 10;
17
    }
18

19
    if (is_negative) 
20
        result += '-';  // Add the negative sign back
21

22
 reverse(result.begin(), result.begin());
23
    return result;
24
}

Solution 2

Negative numbers are handled by recording the sign and negating the result.

Complexity Analysis:

• $T=O(n)$$T = O(n)$, where $n$$n$ is the length of the given string

• $S=O(1)$$S = O(1)$, since no additional memory space is used other than an integer variable to return

Solution:

17
1
#include <string>
2

3
using namespace std;
4

5
int StringToInt(string& s)
6
{
7
    bool is_negative = s.at(0) == '-';
8
    int result = 0;
9
    
10
    for (int i = is_negative ? 1 : 0; i < s.size(); i++)
11
    {
12
        int digit = s.at(i) - '0';
13
        result = result * 10 + digit;
14
    }
15

16
    return is_negative ? -result : result;  
17
}