String to Integer atoi in DSA C++ - Time & Space Complexity

Time Complexity: String to Integer atoi

O(n)

Understanding Time Complexity

We want to understand how the time needed to convert a string to an integer grows as the string gets longer.

How does the number of steps change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int myAtoi(const std::string &s) {
    int i = 0, n = s.size(), sign = 1, result = 0;
    while (i < n && s[i] == ' ') i++;
    if (i < n && (s[i] == '+' || s[i] == '-')) {
        sign = (s[i] == '-') ? -1 : 1;
        i++;
    }
    while (i < n && std::isdigit(s[i])) {
        int digit = s[i] - '0';
        // Check overflow omitted for simplicity
        result = result * 10 + digit;
        i++;
    }
    return sign * result;
}
    

This code converts a string to an integer by skipping spaces, checking sign, and reading digits until non-digit or end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through characters of the string to process spaces, sign, and digits.
• How many times: Each character is visited at most once in order from start to end.

How Execution Grows With Input

As the string length grows, the number of characters to check grows linearly.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The work grows directly in proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "The function runs in constant time because it just converts a number."

[OK] Correct: The function must check each character until it finds a non-digit, so time depends on input length.

Interview Connect

Understanding this helps you explain how simple string parsing scales and shows you can analyze loops carefully.

Self-Check

"What if we changed the code to stop after reading a fixed number of digits? How would the time complexity change?"

Practice

1. What does the atoi function do in C++?

easy

A. Converts a string representing a number into an integer

B. Converts an integer into a string

C. Sorts characters in a string alphabetically

D. Calculates the length of a string

Solution

1. Step 1: Understand the purpose of atoi

   The function atoi stands for ASCII to integer and converts a numeric string to an integer value.

2. Step 2: Differentiate from other string functions

   It does not convert integers to strings, sort strings, or calculate string length.

3. Final Answer:

   Converts a string representing a number into an integer -> Option A

4. Quick Check:

   atoi = string to int conversion [OK]

Hint: Remember atoi means ASCII to integer conversion [OK]

Common Mistakes:

• Confusing atoi with itoa (integer to string)
• Thinking atoi sorts or measures strings
• Assuming atoi handles non-numeric strings safely

2. Which of the following is the correct syntax to use atoi in C++?

easy

A. int num = atoi("1234");

B. int num = atoi(1234);

C. int num = atoi('1234');

D. int num = atoi(\"1234\");

Solution

1. Step 1: Check the parameter type for atoi

   The atoi function expects a C-style string (const char*), so the argument must be a string literal like "1234".

2. Step 2: Analyze each option

   int num = atoi("1234"); passes a string literal correctly. int num = atoi(1234); passes an integer, which is invalid. int num = atoi('1234'); uses single quotes, which denote a char, not a string. int num = atoi(\"1234\"); has escaped quotes incorrectly.

3. Final Answer:

   int num = atoi("1234"); -> Option A

4. Quick Check:

   atoi needs a string literal argument [OK]

Hint: atoi requires a string literal, not a number or char [OK]

Common Mistakes:

• Passing integer instead of string
• Using single quotes instead of double quotes
• Incorrect escaping of quotes

3. What will be the output of the following C++ code?

char str[] = "-42abc";
int val = atoi(str);
std::cout << val << std::endl;

medium

A. 0

B. Runtime error

C. 42

D. -42

Solution

1. Step 1: Understand atoi behavior with non-digit characters

   atoi converts the initial part of the string that forms a valid integer. It stops reading when it encounters a non-digit after the number.

2. Step 2: Analyze the string "-42abc"

   It starts with '-', then '4', '2' which form -42. The characters 'a', 'b', 'c' are ignored after the number.

3. Final Answer:

   -42 -> Option D

4. Quick Check:

   atoi stops at first non-digit after number [OK]

Hint: atoi reads number until non-digit character [OK]

Common Mistakes:

• Expecting atoi to parse entire string including letters
• Assuming atoi returns 0 for strings with trailing letters
• Thinking it throws runtime error on letters

4. Identify the error in the following code snippet that uses atoi:

std::string s = "123";
int num = atoi(s);
std::cout << num << std::endl;

medium

A. Missing header file for atoi

B. atoi requires integer argument

C. Cannot pass std::string directly to atoi

D. No error, code runs fine

Solution

1. Step 1: Check parameter type for atoi

   atoi expects a C-style string (const char*), but s is a std::string object.

2. Step 2: Correct usage

   To use atoi with std::string, call s.c_str() to get a C-style string.

3. Final Answer:

   Cannot pass std::string directly to atoi -> Option C

4. Quick Check:

   atoi needs const char*, not std::string [OK]

Hint: Use s.c_str() to convert std::string for atoi [OK]

Common Mistakes:

• Passing std::string directly to atoi
• Ignoring need for c_str() method
• Assuming atoi accepts std::string

5. You want to convert a string to integer but also handle invalid inputs safely without crashing. Which approach is best in C++?

hard

A. Use atoi and check if result is zero to detect errors

B. Use stoi inside try-catch block to catch exceptions

C. Use atoi and ignore invalid inputs

D. Use printf to print the string and guess the number

Solution

1. Step 1: Understand limitations of atoi

   atoi returns 0 for invalid inputs but cannot distinguish between actual zero and error, so it is unsafe for error handling.

2. Step 2: Use stoi with exception handling

   stoi throws exceptions on invalid input, allowing safe detection and handling of errors using try-catch blocks.

3. Final Answer:

   Use stoi inside try-catch block to catch exceptions -> Option B

4. Quick Check:

   stoi with try-catch is safe for invalid input [OK]

Hint: Use stoi with try-catch for safe string to int conversion [OK]

Common Mistakes:

• Relying on atoi to detect invalid input
• Ignoring exceptions from stoi
• Using printf to guess numbers