Parse a Signed Integer in an Arbitrary Base

Implement a production-style conversion from a signed string to a 32-bit integer in a supplied base.

Implement parse_base_integer(text: string, base: int) -> string. Return the canonical base-10 integer on success. Return INVALID for invalid syntax or an unsupported base, and OVERFLOW for a syntactically valid value outside signed 32-bit range.

Constraints & Assumptions

The source requests arbitrary-base atoi and explicitly notes the negative-number case. The following strict parsing and error policy is an explicit practice contract.

• 2 <= base <= 36 is supported; any other base returns INVALID.
• Input length is at most 100000 characters. Trim only ASCII spaces at the two ends. Internal whitespace, tabs, separators, and trailing non-digit text are invalid. No base prefix is specially recognized or stripped: all characters after the optional sign are interpreted by the digit grammar for the supplied base. Thus 0x1 is valid ordinary digits in base 36 (value 1189), but invalid in base 16 because x is not a base-16 digit.
• After trimming, accept an optional single + or -, followed by at least one digit. Digits are 0–9, a–z, or A–Z, with letters representing 10 through 35, case-insensitively. Every digit value must be less than base.
• The signed range is -2147483648 through 2147483647. Leading zeroes are allowed. Both -0 and +0 return 0.
• Syntax takes precedence over overflow: if any character violates the grammar, return INVALID even if an earlier prefix already overflowed. Otherwise return OVERFLOW if the magnitude is too large.
• Aim for O(length) time and O(1) auxiliary space. Do not depend on arbitrary-precision conversion of the whole input.

Examples

parse_base_integer(" -80000000 ",16) -> "-2147483648"
parse_base_integer("7fffffff",16) -> "2147483647"
parse_base_integer("80000000",16) -> "OVERFLOW"
parse_base_integer("10102",2) -> "INVALID"
parse_base_integer("+000",10) -> "0"
parse_base_integer("0x1",36) -> "1189"
parse_base_integer("0x1",16) -> "INVALID"

Explain validation of empty/sign-only strings and how the negative boundary differs from the positive boundary. Describe how you detect overflow before multiplication and addition.

Hint: Check against a sign-specific magnitude bound

Before appending digit d to accumulated magnitude v, compare v with the largest value for which v * base + d remains allowed. Continue syntax validation after detecting overflow.

Parse a Signed Base Integer with Strict Validation

Approach

Validate the base, then locate the trimmed interval by advancing indices over ASCII space only. Consume at most one leading sign and require at least one following character. Decode each remaining character with explicit ASCII ranges, rejecting all other characters and digit values outside the base. Use magnitude bound 2147483648 for negative inputs and 2147483647 otherwise. Before incorporating digit d, require v <= floor((limit-d)/base); this is exactly the condition v*base+d <= limit and avoids overflow before multiplication. Once exceeded, keep an overflow flag and stop changing the bounded accumulator, but continue checking every later character. A syntax error therefore returns INVALID even after overflow. After complete validation, return OVERFLOW if flagged, or format the signed magnitude in decimal. Formatting zero naturally removes either sign. This invariant bounds arithmetic throughout and never relies on arbitrary-precision whole-input conversion. Indices and a fixed number of numeric variables give constant auxiliary state; C++ takes its argument by value, so its input copy is excluded from that analysis.

• Time complexity: O(n), where n is text length
• Space complexity: O(1) auxiliary space, excluding the C++ value-parameter input copy