Increment an integer string

Question

I was recently asked to increment an integer string in Javascript as part of an interview. I managed to do it, but my code was quite messy. What is a good algorithm for incrementing integer strings by 1 in Javascript (or any language)?

"1"=>"2"
"9"=>"10"
"-10"=>"-9"
"-1"=>"0"
"123456"=>"123457"

This is to prevent integer overflow, so obviously I cannot convert the string to an integer.

Whoever comes up with a solution, please test it with the following code (assuming your function is called inc):

var s = '-1000';
for(var i = -999; i <= 999; i++) {
    s = inc(s);
    if(s !== i.toString())
        throw [s, i];
}

Answer 1

1. Split the string into substrings that are definitely small enough to increment properly.
2. Increment/decrement the last chunk (based on the sign).
3. Carry any overflow into the next chunk—or borrow from the next chunk—until done.
4. Join the integers as strings again.