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 es 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];
}
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 es 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];
}
- 4 You're dealing with integers larger than 9007199254740992 and incrementing them by one? (That would be my first response. "Are you SURE you need this?" :) – Phrogz Commented Feb 4, 2015 at 22:47
- @Phrogz Interview problems are generally a small part of a bigger puzzle. – sarveshseri Commented Feb 4, 2015 at 23:03
- I took liberty to add testing code to your question, because many answers so far don't pass it. – georg Commented Feb 4, 2015 at 23:54
7 Answers
Reset to default 3- Split the string into substrings that are definitely small enough to increment properly.
- Increment/decrement the last chunk (based on the sign).
- Carry any overflow into the next chunk—or borrow from the next chunk—until done.
- Join the integers as strings again.
Since you specifically asked not to convert strings to integers, here is a method that uses only string manipulation function - no parseInt.
To use it just call incrementString('123').
var incrementMapPositive = { '0': '1', '1': '2', '2': '3', '3': '4', '4': '5', '5': '6', '6': '7', '7': '8', '8': '9', '9': '0' };
var incrementMapNegative = { '0': '9', '9': '8', '8': '7', '7': '6', '6': '5', '5': '4', '4': '3', '3': '2', '2': '1', '1': '0' };
function incrementString(str, pos) {
if (!str)
return '';
// handle case '-0'
if (/^-0+$/.test(str))
str = '0';
// position count starts from the end, so get the proper index
var posFromStart = str.length - 1 - (pos || 0);
// get the character to increment (use the last one if none specified)
var chr = str.charAt(posFromStart);
var isNegative = str.charAt(0) === '-';
var incrementMap = isNegative ? incrementMapNegative : incrementMapPositive;
// if the very first digit is carried (e.g. incrementing from 99 to 100), we need to add a '1'
var newChr = !chr ? '1' : incrementMap[chr];
// build the new string with the replaced digit
var incremented = str.substr(0, posFromStart) + newChr + str.substr(posFromStart + 1);
// detect if we need to carry/borrow from the next digit
if (!isNegative && newChr === '0' || isNegative && newChr === '9')
incremented = incrementString(incremented, (pos || 0) + 1);
//clean leading zeros
incremented = incremented.replace(/^(-)?0+/, '$1');
if (incremented === '-')
incremented = '0';
return incremented;
}
EDIT: replaced if-else blocks with a mapping object. Also incrementing correctly negative numbers now.
EDIT 2: made some cleanup and added some inline ments to better explain code.
EDIT 3: handling case '-0'
To handle carrying correctly, you could use something like:
function replaceChar(str, index, character) {
return str.substr(0, index) + character + str.substr(index + character.length);
}
function incStr(str) {
var carry = false;
var ret = str;
for (var i = str.length; i > 0; --i) {
var inc = str.charCodeAt(i - 1);
if (i === str.length) {
++inc;
}
if (carry) {
++inc;
}
if (inc > 58) {
carry = true;
ret = replaceChar(ret, i - 1, "1");
} else if (inc === 58) {
carry = true;
ret = replaceChar(ret, i - 1, "0");
} else {
carry = false;
ret = replaceChar(ret, i - 1, String.fromCharCode(inc));
}
};
if (carry) {
return "1" + ret;
} else {
return ret;
}
}
var testData = ["13", "14", "19", "20", "300", "08974871238471923501", "999999999999999999999999999"];
var results = testData.map(function(it) {
return incStr(it);
});
document.getElementById("results").textContent = JSON.stringify(results);<pre id="results"></pre>It's definitely not the prettiest implementation, as it creates a lot of strings along the way (at least one for each digit in the input), but it will run with linear speed (depending on the input length) and won't balloon in memory for large values.
There is not a single actual string-to-number conversion, as we know that the ten valid digits ([0-9]) e in order, and we can simply increment the character code. If it goes beyond 9 (followed by :), then we check:
- If it's greater than
'9'+1, we're carrying and hit the initial increment, so the digit should be one and we carry. - If it's greater than
'9', we're carrying, so the digit should be zero and we carry. - Otherwise, we didn't wrap, so replace the digit but don't carry.
This code works for both positive and negative numbers - nothing simple, but self explanatory. Good luck with the job..
var tests = ['9007199254740992','999999999999999999','-999999999','-0','-80','800','99']
function addOne(num){
if (Math.abs(parseInt(num,10)) == 0){return '1'};
var numArray = num.split(''),
answer = [];
var sign = 1;
if (numArray[0] == '+' || numArray[0] == '-'){
if (numArray[0] == '-'){sign = -1};
numArray.splice(0,1);
}
var idx = numArray.length;
var next_int = 0;
var carry = 1; /* first add 1 */
while(idx-- && carry != 0){
next_int = parseInt(numArray[idx],10) + (sign * carry);
if (sign > 0){
answer[idx] = (next_int >= 10 ? next_int - 10 : next_int)
carry = (next_int >= 10 ? 1 : 0)
} else {
answer[idx] = (next_int == -1 ? 9 : Math.abs(next_int));
carry = (next_int == -1 ? 1 : 0)
}
if (carry == 0){
while(idx--){
answer[idx] = numArray[idx]
}
}
}
if (sign > 0){
return (carry == 0 ? answer.join('') : carry + answer.join(''));
} else {
return ('-' + answer.join(''));
}
}
for (var i = 0;i<tests.length;i++){
console.log (' Num In: ' + tests[i] + ' Num Out: ' + addOne(tests[i]));
}
Num In: 9007199254740992 Num Out: 9007199254740993
Num In: 999999999999999999 Num Out: 1000000000000000000 /* bigger than big */
Num In: -999999999 Num Out: -999999998
Num In: -0 Num Out: 1
Num In: -80 Num Out: -79
Num In: 800 Num Out: 801
Num In: 99 Num Out: 100
Lets look at the last value which has precision as a Number in JavaScript when added to.
var s = ""+Number.MAX_SAFE_INTEGER;
And add one to it.
s++;//"9007199254740992"
Now the next increment will fail to add value. In order to increment, there needs to be some tweak involved. The benefit is that incrementing by 1 allows some basic assumptions to be made. Basically which is no number to the left of 9 has a chance of being changed.
//defined
function inc(num,i){
i = i == undefined ? 1 : i;
var c = num[num.length-i];
var left = num.substr(0,num.length-i);
var right = num.substr(num.length-i+1);
if( c == 9 ){
return inc(left+0+right,i+1);
}else{
return left+(+c+1)+right;
}
}
//used
var s = ""+(Number.MAX_SAFE_INTEGER+1);//"9007199254740992"
for(var i = 0; i < 10; i++){
s = inc(s);
}
alert(s);//"9007199254741002"My strategy
- Put each digit as a integer in an array
- increment right hand side by one
- work backwards carrying
- add a 1 if overflow at left hand side
- for negatives model as subtraction i.e. -2 + 1 is actual -(2 - 1)
Code
function inc(str) {
var parts = [];
var i = 0;
var negative = str[0] === '-';
for (i = negative ? 1 : 0; i < str.length; i++) {
parts.push(str.charCodeAt(i) - 48);
}
parts[parts.length - 1] += (negative ? -1 : 1);
for (i = parts.length - 1; i >= 0; i--) { // carry right to left
if (parts[i] > 9) { // overflow
parts[i] = 0;
if (i > 0) {
parts[i - 1]++;
} else {
parts.unshift(1); // 99 -> 100 case
}
} else if (parts[i] < 0) { // underflow
parts[i] = 9;
if (i > 0) {
parts[i - 1]--;
} else {
parts.shift(); // 100 -> 99 case
}
}
}
if (negative) {
parts.unshift("-");
}
return parts.join('');
}
My approach would be a maybe memory-intensive one using array methods:
var num = '12345';
var newNum = num.split('').map(function(el){
return ''+(++el);
}).join('');
EDIT
forgot to think about carry - moment please^^
var num = '278889';
var newNum;
var temp = num.split('').reverse().reduce(function(carry, el){
// carry[0] holds the carry from last operation, carry[1] is our new num
// ~~num is same as Math.float() or in this case paseInt
++el;
el += carry[0];
return [ ~~(el / 10), (el % 10) + '' + carry[1] ];
}, [0,'']);
// We have to check if last carry was zero or not
newNum = (temp[0] != 0 ? temp[0] : '') + temp[1];
// outputs ["390000"]
console.log([newNum]);