The O(n) Club: Add Strings — When Java Says ‘No Cheating’, Do This

The O(n) Club: Add Strings — When Java Says ‘No Cheating’, Do This

⚡ TL;DR

Add two monster-sized numbers given as strings. You can’t convert to int or touch BigInteger — so you’ll play human calculator with a loop and carry, right-to-left. Java’s not your friend today!

// Wishful thinking (forbidden in interviews):
int n1 = Integer.parseInt(num1);
int n2 = Integer.parseInt(num2);
return String.valueOf(n1 + n2); // Oops — interviewer has left the chat.

🧠 How Devs Usually Mess This Up

If your brain says parseInt() or you let BigInteger sneak in, congrats: you’ve just failed the only rule that mattered. Also, forgetting to handle the final carry, or collecting digits in the wrong order (reversal, anyone?), turns your code into a logic pretzel. Don’t pad with zeros — just pretend missing digits are ‘0’ because… that’s what real humans do after their second coffee.

🔍 What’s Actually Going On

This is elementary school math without the risk of being called to the chalkboard. Move two pointers from the end of each string. For each step, add the current digits and any leftover carry, just like you did with your fingers back in the day. When one string runs out, you treat its digit as zero. Slam the sum’s ones-place into your answer, update the carry, and repeat. At the end, if you skip the reversal step, cue the facepalm.

🛠️ PseudoCode

• Let i be the last index of num1, j be the last index of num2
• Initialize carry = 0 and an empty StringBuilder for your answer
• While either i or j is in bounds, or carry is non-zero:
  • Get num1.charAt(i) - '0' if i valid, else 0
  • Get num2.charAt(j) - '0' if j valid, else 0
  • sum = digit1 + digit2 + carry
  • Append sum % 10 to StringBuilder
  • carry = sum / 10
  • Decrement i and j
• Reverse StringBuilder and return as string

💻 The Code

public String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;
    while (i >= 0 || j >= 0 || carry != 0) {
        int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;
        int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        int total = d1 + d2 + carry;
        sb.append(total % 10);
        carry = total / 10;
        i--;
        j--;
    }
    return sb.reverse().toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Carry Overboard: Don’t forget a leftover carry, or you’ll lose digits at the edge. (Looking at you, 9+9!)
• Reverse Psychology: You must reverse the StringBuilder at the end — or your result is mirror-universe wrong.
• Uneven Inputs: Numbers can be different lengths; don’t pad, just pretend non-existent digits are zero.
• Time/Space: Both are linear in the longer input. No behind-the-scenes magic, no unexpected drama.

🧠 Interviewer Brain-Tattoo

“If you can’t add two strings like a sleep-deprived accountant, you can’t do crypto or finance. Turns out, your elementary math teacher was prepping you for LeetCode.”