0

I was asked this in an interview question to come up with a method that takes in a string like "999" and then increments it by 1, and then returns a new string like "1000".

He said the constraint was you cannot convert directly from string to integer, although you can convert a character into an integer.

I understand that it's rather simple code for a case like "488" where you just have the last character '8', convert it to integer to increment and return "489".

But how do you do the carry over logic for a case like "999"?

Terry Bu
  • 889
  • 1
  • 14
  • 31
  • 1
    See this question (it's about strings with hexadecimal numbers, but the solution is the same) http://stackoverflow.com/questions/31486470/javascript-convert-24-digit-hexadecimal-number-to-decimal-add-1-and-then-conv/31486670#31486670 – m69's been on strike for years Aug 24 '15 at 02:08

4 Answers4

3

How do you carry over from "199" to "200"? If you already solved that, then "999" just means to add a "1" to the beginning after you carry over the other values to zeroes. "999" -> "000" -> "1000".

Update

You can do it without ever using an int. Convert String to char[]. Start from the end. If the last character is between '0' and '8', add one to the character and return the array as a String, otherwise change the '9' to a '0' and repeat for digit before that. If you get to the beginning, then return "1" + chars.

Andreas
  • 154,647
  • 11
  • 152
  • 247
3

Start from the back, and with carry one. Get the digit; add carry to it. If it's now 10, make it a zero, and carry one; otherwise carry is zero. Convert to character. Repeat with all digits going backwards. Finally prepend carry if not zero. (You can stop early and just copy the remaining digits if you ever get carry of zero.)

Amadan
  • 191,408
  • 23
  • 240
  • 301
  • 1
    Watch out for the sign - if its negative, you need to subtract one from the digits rather than add one, and watch for underflow to -1 instead of overflow to 10. – Michael Anderson Aug 24 '15 at 03:11
0

Here you go http://jsfiddle.net/c74vqvan/ .

var s = '999';
var total = '';
var carryTheOne = true;

for(var i = s.length-1; i >= 0; i--)
{
    var intValue = s.charAt(i);
    if(carryTheOne)
    {
        intValue++;
    }
    carryTheOne = intValue == 10;
    if(carryTheOne)
    {
        intValue = 0;
    }
    total = intValue + total;
}

if(carryTheOne) total = '1' + total;

alert(total);
raduation
  • 792
  • 5
  • 11
  • That's JavaScript. The question is for Java. – Andreas Aug 24 '15 at 02:15
  • 3
    Consider it pseudocode for how you can do it in Java. – raduation Aug 24 '15 at 02:20
  • Yeah, but in Java you should never do a loop like that, that would do a `String = digit + String` inside the loop. That is a very bad code smell. In JavaScript, sure, but not in Java. Language matters. – Andreas Aug 24 '15 at 02:25
  • 2
    Oh lord, it really is just demonstrating the logic of how you would do it. In Java you would never do a loop that appends to a String?? I'm not sure where you get this from. – raduation Aug 24 '15 at 02:28
  • If you need to append (not prepend) to a string inside a loop, you use a `StringBuilder`. You don't do it on a `String`. To a Java programmer, that is code smell, and if I was an interviewer, that would cost you 'points'. – Andreas Aug 24 '15 at 02:32
  • 2
    Again, my example was NOT about the language features of Java. It was about the logic of incrementing an integer string one character at a time. You must be a hard interviewer! – raduation Aug 24 '15 at 02:37
-1

What you can do is individually convert each character into an integer. So take the last character (in the "ones" position), convert it to an integer and store it. Take the 2nd-to-last character (in the "tens" position), convert that to an integer, multiply it by 10, and add that to the total. Rinse and repeat. Then add one, and reverse the process by dividing by 10 to "pop" each number off.

Ryan K
  • 3,985
  • 4
  • 39
  • 42
  • This ends up converting the whole string to an integer, albeit manually. Question said "without converting whole string to int". – Andreas Aug 24 '15 at 02:14
  • @Andreas question actually said "you cannot convert directly from string to integer, although you can convert a character into an integer". Thus, I did. – Ryan K Aug 24 '15 at 02:30
  • I was quoting the title. – Andreas Aug 24 '15 at 02:33