UVA Problem 713 – Adding Reversed Numbers Solution

UVA Problem 713 – Adding Reversed Numbers Solution:


Click here to go to this problem in uva Online Judge.

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.

The problem can be solved in a few ways. One which is reversing two string. Then added leading 0’s to the smaller string then adding and printing the result.

Another method is to add trailing 0’s to smaller string if their length differ. Then add them and print the result if starting from left most column. Other wise print result in reverse if calculating from right most column.


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,
 *            Add padding or add leading 0's to given string,
 *            Discard leading or trailing 0's in string,
 *            Shift characters in string by given number of spaces,
 *            add two character array or strings,
 *            Adding very large numbers.
 ***********************************************************************/


#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
     * by calculated padding.
     *
     * 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)
        number[i + padding] = number[i];


    /**
     * Add leading 0's to empty places in the string.
     */
    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
     * and leading zeros.
     */
    char* tempNumber = new char[N];
    int k = 0, i;


    /**
     * Only discards leading zeros and not any other internal zeros.
     */
    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){

        // Add two number
        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';


    /**
     * Discard any leading 0's before printing. Only discards leading 0's and nothing else.
     */
    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);


        /**
         * Add padding to the strings calling fixlength function.
         * 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.
         */
        add(firstNumber, secondNumber, maxlen, maxlen);

    }

	return 0;
}

4 thoughts on “UVA Problem 713 – Adding Reversed Numbers Solution

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s