Parsing numeric arguments - Time & Space Complexity

Time Complexity: Parsing numeric arguments

O(n)

Understanding Time Complexity

When parsing numbers from strings, it is important to know how the time needed grows as the input gets longer.

We want to find out how the work changes when the number has more digits.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int parseNumber(const char *str) {
    int result = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] < '0' || str[i] > '9') break;
        result = result * 10 + (str[i] - '0');
    }
    return result;
}
    

This code reads a string character by character and converts the digits into an integer number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that reads each character in the string.
• How many times: Once for each character until a non-digit or end of string is found.

How Execution Grows With Input

As the number of digits in the string grows, the loop runs longer, doing more work.

Input Size (n)	Approx. Operations
10	About 10 loop steps
100	About 100 loop steps
1000	About 1000 loop steps

Pattern observation: The work grows directly with the number of digits; double the digits means double the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to parse grows in a straight line with the length of the input string.

Common Mistake

[X] Wrong: "Parsing a number always takes constant time because numbers are small."

[OK] Correct: The time depends on how many digits the number has, not the value itself. Longer numbers take more steps.

Interview Connect

Understanding how parsing time grows helps you write efficient input handling and shows you can think about performance clearly.

Self-Check

"What if we changed the code to parse hexadecimal numbers instead of decimal? How would the time complexity change?"

Practice

1. What does the atoi function do in C when parsing numeric arguments?

easy

A. Converts a string to an integer without error checking

B. Converts a string to a floating-point number

C. Checks if a string contains only digits

D. Parses a string and returns a pointer to the next character

Solution

1. Step 1: Understand atoi function purpose

   atoi converts a string to an integer but does not check for errors or invalid input.

2. Step 2: Compare with other parsing functions

   Unlike strtol, atoi does not provide error detection or pointer to next character.

3. Final Answer:

   Converts a string to an integer without error checking -> Option A

4. Quick Check:

   atoi = simple integer conversion [OK]

Hint: Remember: atoi converts but doesn't check errors [OK]

Common Mistakes:

• Thinking atoi checks for invalid input
• Confusing atoi with strtol
• Assuming atoi returns pointer to next char

2. Which of the following is the correct syntax to parse a string "1234" to an integer using strtol in C?

easy

A. int num = strtol("1234", NULL, 10);

B. long num = strtol("1234", NULL, 10);

C. long num = atoi("1234", NULL, 10);

D. int num = strtol("1234", 10, NULL);

Solution

1. Step 1: Check strtol return type

   strtol returns a long, so the variable must be long.

2. Step 2: Verify argument order

   Arguments are: string, pointer to char* for end, and base (10 for decimal). So strtol("1234", NULL, 10) is correct.

3. Final Answer:

   long num = strtol("1234", NULL, 10); -> Option B

4. Quick Check:

   strtol returns long, args: string, endptr, base [OK]

Hint: Remember strtol returns long, not int [OK]

Common Mistakes:

• Using int instead of long for strtol result
• Mixing argument order in strtol
• Using atoi syntax with strtol

3. What will be the output of this C code snippet?

#include 
#include 

int main() {
    char *str = "42abc";
    char *endptr;
    long val = strtol(str, &endptr, 10);
    printf("%ld %s\n", val, endptr);
    return 0;
}

medium

A. Error

B. 0 42abc

C. 42abc (null)

D. 42 abc

Solution

1. Step 1: Understand strtol parsing behavior

   strtol converts initial numeric part "42" to long and sets endptr to point after parsed number, which is "abc".

2. Step 2: Analyze printf output

   It prints the number 42 and then the string starting at endptr, which is "abc".

3. Final Answer:

   42 abc -> Option D

4. Quick Check:

   Parsed number + leftover string = 42 abc [OK]

Hint: Check where endptr points after strtol [OK]

Common Mistakes:

• Assuming strtol parses entire string
• Ignoring endptr usage
• Expecting error on non-digit suffix

4. Identify the error in this code snippet that parses a numeric argument:

#include 

int main(int argc, char *argv[]) {
    int num = atoi(argv[1]);
    if (num == 0) {
        printf("Invalid number\n");
    }
    return 0;
}

medium

A. Missing check if argc > 1 before accessing argv[1]

B. Using int instead of long for atoi result

C. atoi returns 0 for invalid input and valid zero, causing confusion

D. No error, code is correct

Solution

1. Step 1: Check argument count before access

   The code uses argv[1] without verifying argc > 1, risking out-of-bounds access.

2. Step 2: Understand atoi zero ambiguity

   While atoi returns 0 for invalid input and valid zero, the bigger issue is missing argument check causing runtime error.

3. Final Answer:

   Missing check if argc > 1 before accessing argv[1] -> Option A

4. Quick Check:

   Always check argc before argv access [OK]

Hint: Always check argc before argv usage [OK]

Common Mistakes:

• Ignoring argc check leads to crashes
• Confusing atoi zero return meaning
• Assuming atoi handles errors

5. You want to safely parse a command-line argument as a positive integer in C. Which approach correctly handles invalid input and zero?

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    if (argc <= 1) {
        printf("No input provided\n");
        return 1;
    }
    char *endptr;
    long val = strtol(argv[1], &endptr, 10);
    if (*endptr != '\0' || val <= 0) {
        printf("Invalid positive integer\n");
        return 1;
    }
    printf("Parsed value: %ld\n", val);
    return 0;
}

hard

A. Fails to check if argv[1] is NULL before parsing

B. Does not handle negative numbers correctly

C. Correctly parses positive integers and rejects invalid or zero input

D. Should use atoi instead of strtol for safety

Solution

1. Step 1: Check argument count

   The code checks if argc <= 1 to ensure input is provided.

2. Step 2: Use strtol with endptr to detect invalid characters and check if value is positive

   It verifies *endptr == '\0' to confirm full string parsed and val > 0 to ensure positive integer.

3. Final Answer:

   Correctly parses positive integers and rejects invalid or zero input -> Option C

4. Quick Check:

   strtol + endptr + value check = safe parsing [OK]

Hint: Use strtol with endptr and check value > 0 [OK]

Common Mistakes:

• Using atoi which can't detect invalid input
• Not checking endptr for leftover chars
• Ignoring zero or negative values