415. Add Strings
1. Description
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
2. Note
- The length of both num1 and num2 is < 5100.
- Both num1 and num2 contains only digits 0-9.
- Both num1 and num2 does not contain any leading zero.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
3. Solutions
My Accepted Solution
n = max(m_num1.size(), m_num2.size())
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// string addStrings(string num1, string num2)
string addStrings(string &m_num1, string &m_num2)
{
// let m_num1 be the result
if(m_num1.size() < m_num2.size()) swap(m_num1, m_num2);
int carry = 0;
for(int i = m_num1.size() - 1, j = m_num2.size() - 1; i >= 0 && (j >= 0 || carry); i--, j--)
{
int sum = ((m_num1[i] - '0') + ((j >= 0 ? m_num2[j] : '0') - '0') + carry) % 10;
carry = ((m_num1[i] - '0') + ((j >= 0 ? m_num2[j] : '0') - '0') + carry) / 10;
m_num1[i] = sum + '0';
}
if(carry) m_num1.insert(0, "1");
return m_num1;
}
};