# UVA Problem 713 – Adding Reversed Numbers Solution

UVA Problem 713 – Adding Reversed Numbers Solution:

Solving Technique:

The biggest problem in this problem is that there is no built in data type to hold 200 digit numbers. Although this problem is good in sense that it says that the number can be 200 characters long.

To handle this large number array is needed. while others may have solved using integer array and their methods may be faster. But mine addition is using character array.

##### For example using first method,

when input is 24 and 1, their reversal is,

```42
01
==
43
```

Since i am using right most column as 0 th index. So the result will be 34.

Again for input 4358 and 754,

```8534
0457
====
8991
```

Result will be 1998. This is because i am starting calculation from rightmost column and moving carry to left.

##### Another method is adding as is then print result from left,
```4358
7540
====
1998
```

I’ve implemented the first method only. The code is explained in comments.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

```3
24 1
4358 754
305 794
```

Output:

```34
1998
1
```

### Code:

```/***********************************************************************
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 1225 - Digit Counting
* Technique: Reverse string or character array,
*            Shift characters in string by given number of spaces,
*            add two character array or strings,
***********************************************************************/

#include<stdio.h>
#include<string.h>

#define N 512

static char* firstNumber;
static char* secondNumber;

static char input[N];

/*********************************************************************
* Pass a string and a Integer length greater than the String length.
* The function will add leading 0's to the string. The length of the
* new string will be equal to the passes integer.
*********************************************************************/
char* fixLength(char* number, int maxlen){

/**
* Calculate padding or the amount positions to shift digits to the right.
* If length of string is 5 and maxlen is 8 then each digit starting from
* the end will be shifted 3 places to the right.
*
* Ex: Original String = "25634", Modified String = "00025634"
*/
int numLength = strlen(number);
int padding = maxlen - numLength;

/**
* Starting from the end of given string shift each character to the right
*
* Character are shifted from rear otherwise beginning from 0 index will
* replace existing character in the string and output string will be garbage.
*/
for(int i = numLength - 1; i >= 0; --i)

/**
*/
for(int i = 0; i < padding; ++i)
number[i] = '0';

/**
* Mark end of String
*/
number[maxlen] = '\0';

return number;
}

/*********************************************************************
* Given a string and its length this function reverses the string.
* It first discards any leading 0's in the input string then reverses
* the input string.
*********************************************************************/
char* reverseString( char* number, int len ){

/**
* Initialize a new char array to keep the string after discarding
*/
char* tempNumber = new char[N];
int k = 0, i;

/**
*/
for(i = 0; i < len; ++i)
if(number[i] - '0') break;
for(; i < len; ++i)
tempNumber[k++] = number[i];
tempNumber[k] = '\0';

/**
* Reverse the new string without leading zeros.
*/
int tmp = k / 2;
for(int i = 0, j = k - 1; i < tmp; ++i, --j){
int swap = tempNumber[i];
tempNumber[i] = tempNumber[j];
tempNumber[j] = swap;
}

return tempNumber;
}

/**********************************************************************************
* Starting from the last column add two integers. Then add any carry to the left
* column. This way calculate the addition. In the end if any carry left add it
* to the output char array. For safety assume last carry can be bigger than one
* digit.
**********************************************************************************/
void add( char* firstNumber, char* secondNumber, int lengthFirst, int lengthSecond){

/**
* Initialize a new array to keep sum of two number strings.
*/
char* tempNumber = new char[N];
int k = 0;
int sum = 0;
int carry = 0;

/**
* Starting from last column move left to 0th index. Add the numbers and if there
* is carry add it to left column.
*/
for(int j = lengthFirst - 1; j >= 0; --j){

sum = firstNumber[j] - '0' + secondNumber[j] - '0';

// Add if any previous carry
sum = sum + carry;

// place the part of output number
tempNumber[k++] = (sum % 10) + '0';

// calculate the the carry
carry = sum / 10;
}

/**
* Assuming last carry can be more than one digit. Add carry digits to output array.
*/
while(carry){
tempNumber[k++] = (carry % 10) + '0';
carry /= 10;
}
tempNumber[k] = '\0';

/**
*/
int p = 0;
for(; p < k; ++p)
if(tempNumber[p] - '0') break;

for(; p < k; ++p)
printf("%c", tempNumber[p]);
printf("\n");

}

int main() {

/**
* Important allocate memory for the numbers.
*/
firstNumber = new char[N];
secondNumber = new char[N];

int n;

scanf("%d", &n);
getchar();

while(n--){

int j = 0, k = 0;

/**
* Take input of two numbers as strings.
*/
scanf("%s%s", firstNumber, secondNumber);

/**
* Get each of their length.
*/
int firstNumberLength = strlen(firstNumber);
int secondNumberLength = strlen(secondNumber);

/**
* Initial guess the first number string is bigger.
*/
int maxlen = firstNumberLength;

/**
* Reverse both of the number string.
*/
firstNumber = reverseString(firstNumber, firstNumberLength);
secondNumber = reverseString(secondNumber, secondNumberLength);

/**
* Pass in the smaller number string and bigger number string size.
*
* If initial guess of first number is bigger is wrong then update
* the max length with second number length.
*/
if( firstNumberLength < secondNumberLength ){
firstNumber = fixLength(firstNumber, secondNumberLength);
maxlen = secondNumberLength;
}
else
secondNumber = fixLength(secondNumber, firstNumberLength);

/**
* Now pass in the two numbers and max length to add them and print answer.
* Notice here i pass the same argument twice this need to be fixed and also
* there are many more improvements needed in other functions.
*/