Adding Reversed Numbers - ADDREV on SPOJ

Question

Today I tried solving this problem on SPOJ, in which you reverse the digits of two numbers, add them, and print the reversed digits of the sum. (When reversing, leading zeroes in the result should be dropped, and trailing zeroes in the result shouldn't happen.)

I used C++ to write the code for this problem. My code got accepted in the first go and I was happy about it but I feel my code is way too long for a problem of this kind. I would like some suggestions on how to reduce the code and make it more readable at the same time.

#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

using namespace std;

#define ALL(C)  (C).begin(), (C).end()
#define LN(str) (int)(str).length()

// this function gets the reversed form of the input number, the function is coded assuming that the input number has both trailing and leading 0's
string getReverseNum(string& num) {  

  string reversedNum = "";
  // find the index of last leading 0
  int index1 = -1;
  for(int i = 0; i < LN(num); ++i) {
     if(num[i] == '0')
        continue;
     else {
    index1 = i;
    break;
     }
  }

  // find the index of the first trailing 0
  int index2 = -1;
  for(int i = LN(num)-1; i >= 0; --i) {
    if(num[i] == '0')
     continue;
    else {
       index2 = i+1;
       break;
    }
  }

  reversedNum = num.substr(index1, index2-index1);

  if(reversedNum == "")
    return "0";
  return reversedNum;
}

// this function is used to convert an integer to a string
string convertIntToString(int num) {

  ostringstream oss;
  oss << num;
  return oss.str();
}

// this function is used to add the two input numbers and return the result as a string
string addNumbers(string& num1, string& num2) {

  int carry = 0;
  string result = "";

  for(int i = 0; i < LN(num2); ++i) {
    int dig1 = num1[i]%48;
    int dig2 = num2[i]%48;
    int temp = dig1+dig2+carry;
    carry = temp/10;
    result += convertIntToString(temp%10);
  }

  for(int i = LN(num2); i < LN(num1); ++i) {
    int dig = num1[i]%48;
    int temp = dig+carry;
    carry = temp/10;
    result += convertIntToString(temp%10);
  }

  if(carry != 0)
   result += convertIntToString(carry);

  return getReverseNum(result);
}

// this function is used to return the reversed sum of the two input numbers it receives as parameters
string getReversedSum(string& num1, string& num2) {

  // first we get the reverse of two numbers
  string reversedNum1 = getReverseNum(num1);
  string reversedNum2 = getReverseNum(num2);  

  string reversedNum = "";

  int len1 = LN(reversedNum1), len2 = LN(reversedNum2);

  if(len1 < len2)
    return addNumbers(reversedNum2, reversedNum1);
  return addNumbers(reversedNum1, reversedNum2);

}

int main() {

  // this variable stores the number of test cases on which the program is run
  int N;
  cin >> N;

  // clear the input stream
  cin.ignore();

  // program execution begins here
  while(N--) {
    string num1, num2;
    cin >> num1 >> num2;
    cout << getReversedSum(num1, num2) << endl;         
  }
  return 0;
}

Code is hosted here.

Answer 1

A few notes:

• Why do you have a bunch of extra headers at the top? This extra cruft (such as the vector class), is going to cost you a bit of extra compile time for nothing plus it adds to the length of your code. Cut back on the stuff you don't need; I found you only needed two of the headers out of the seven you have in your code.

• Here are the woes of using namespace std;. Please try to get into the habit of not using it.

• Your #define's are interesting, but I found them a bit useless really. They somewhat obscure the readability of the program as well, and should be removed IMO.

• Your getReverseNum() function really just reverses a std::string object... but there's a standard library function std::reverse() that does this task for you (it's likely that this function is more efficient as well).

• In C++, you should almost never use out parameters (variables taken by reference and used to return a value from a function), you can read this excellent article by Eric Niebler. There are few cases where out parameters can make sense:

  • When you want your return to be fast. And even then, return value optimization and move semantics may still be faster.

  • When you have several output values. For example, you want to assign a value to a function and return whether it succeeded:

    bool assign(int from, int& to)
    {
        if (from != 0)
        {
            to = from;
            return true;
        }
        return false;
    }
    

    But even for this situation, there are better solutions such as boost:optional to return both a value and whether it succeeded or not. And if you need several error values, use exceptions. And if you need to actually return several values, you general want to pack them into a dedicated struct or a std::tuple.

  • Input-output parameters: sometimes, you want to take a parameter, read from it, and then write to it again. That is still a valid use case (but these are not strict out parameters anymore).

  Overall, for your case it would be better to remove the reference parameters as they serve no purpose really and could be hurting performance.

• Your addNumbers() function could be simplified with the use of the standard functions std::stoi, std::to_string, and std::string::erase, along with our old friend std::reverse.

• Your variable N in your main() function is somewhat confusing as to what it's purpose is at first. I found it better named as cases.

---

Final Code:

#include <string>
#include <iostream>

std::string getReversedSum(std::string num1, std::string num2)
{
    // first we reverse the two numbers
    std::reverse(std::begin(num1), std::end(num1));
    std::reverse(std::begin(num2), std::end(num2));

    // convert the strings to ints so we can add them, then back to a string
    std::string sum = std::to_string(std::stoi(num1) + std::stoi(num2));

    // reverse the string and erase the leading zeros
    std::reverse(std::begin(sum), std::end(sum));
    sum.erase(0, sum.find_first_not_of('0'));
    return sum;
}

int main()
{
    int cases = 0;
    std::cin >> cases;

    // clear the input stream
    std::cin.ignore();

    while(cases--)
    {
        std::string num1;
        std::string num2;
        std::cin >> num1 >> num2;
        std::cout << getReversedSum(num1, num2) << std::endl;
    }
}

Answer 2

Trying to do arithmetic using strings is a pain. The only point of using strings would to make use of int-to-string and string-reversal routines, and you aren't even doing that advantageously.

The solution would be so much simpler if your numbers were in int form.

#include <iostream>

int reverse(int n) {
    int rev = 0;
    for (; n; n /= 10) {
        rev = 10 * rev + (n % 10);
    }
    return rev;
}

int getReversedSum(int num1, int num2) {
    return reverse(reverse(num1) + reverse(num2));
}

int main() {
    int n;
    std::cin >> n;
    std::cin.ignore();

    while (n--) {
        int num1, num2;
        std::cin >> num1 >> num2;
        std::cout << getReversedSum(num1, num2) << std::endl;
    }
}

Answer 3

Readability and Maintainability

  string reversedNum = "";

This is never used in getReversedSum.

  int len1 = LN(reversedNum1), len2 = LN(reversedNum2);

  if(len1 < len2)
    return addNumbers(reversedNum2, reversedNum1);
  return addNumbers(reversedNum1, reversedNum2);

I would find this easier to read as

  if (reversedNum1.length() < reversedNum2.length()) {
    return addNumbers(reversedNum2, reversedNum1);
  }

  return addNumbers(reversedNum1, reversedNum2);

You don't use the lengths again, so there is no point in storing them.

Your LN macro makes the code harder to read for a small reduction in code typed. It doesn't seem worth it. Also, macros are a C thing. In C++, you'd generally use inline functions instead.

You also may want to consider making addNumbers a private class function. The reason being that it relies on always being called with the length of the first string being less than or equal to that of the second. Otherwise, it would be better to put this logic inside addNumbers to gate against the possibility of it being called incorrectly.

Don't lie to me

// this function gets the reversed form of the input number, the function is coded assuming that the input number has both trailing and leading 0's
string getReverseNum(string& num) { 

But that's not what this function does. Call it with getReverseNum("54") and you'll get 54, not 45. A better name for this would be trim.

// trim leading and trailing zeroes
string trimZeroes(const string& num) { 

Note that I added the const keyword. This allows us to call it trimZeroes("54").

Avoid magic numbers

int dig1 = num1[i]%48;
int dig2 = num2[i]%48;

What's 48 here? I'm guessing that it's the ASCII value of '0'. Why not just say that?

int digit1 = num1[i] - '0';
int digit2 = num2[i] - '0';

I also changed it to subtraction rather than calculating the remainder of a division. I find that easier to follow. It's also easier to debug bad inputs (e.g. "ai" is the same as "19" in the original code).

Converting to string unnecessary

// this function is used to convert an integer to a string
string convertIntToString(int num) {

  ostringstream oss;
  oss << num;
  return oss.str();
}

You don't actually need to convert an integer to a string. You're appending digits to the end of the string one-by-one. You can convert to a character. I.e.

    result += convertIntToString(temp%10);

would become

    result += temp%10 + '0';

You could create a function for this if you want. There's a good chance that the function will get inlined as it's rather trivial.

char convertToCharacter(int digit) {
  return digit + '0';
}

Keep it simple

     if(num[i] == '0')
        continue;
     else {
    index1 = i;
    break;
     }

Why use a continue there? Instead

     if (num[i] != '0') {
       index1 = i;
       break;
     }

does the same thing with less code.