UVA Problem 10018 – Reverse and Add Solution

UVA Problem 10018 – Reverse and Add Solution:


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

Solution Technique:

This problem requires summing a (big) integer and its reversed form then check it the result is palindrome or not. If the result is not palindrome then continue the same process with the result now as the input.

Also for each attempt trying to check if the number is palindrome increase the iteration count. which is the first part of the output. If the number is palindrome print the iteration and a space followed by the palindrome integer.

I have made a simple diagram to show this,

uva 10018 Reverse and Add Solution diagram
uva 10018 Reverse and Add Solution diagram

All the results from calculation will fit in a long long integer. In C an unsigned long or long long should suffice. So no need to use arrays to calculate and store results.

 

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++.


Input:

3
195
265
750

 


Output:

4 9339
5 45254
3 6666

Code:

/**
 * Author:     Quickgrid ( Asif Ahmed )
 * Site:       https://quickgrid.wordpress.com
 * Problem:    UVA 10018 - Reverse and Add
 * Techniques: Reverse Integer, Integer into Reversed String, Palindrome Check
 */

#include<stdio.h>

/**
 * Reverses a given long long integer.
 */
long long reverseNumber(long long input) {

    long long reversed = 0;

    // Reverse a given integer.
    while(input) {
        reversed = reversed * 10 + (input % 10);
        input /= 10;
    }

    return reversed;

}



static char resultString[16];


/**
 * Converts the input integer to String and Checks if the String is palindrome.
 * Since this is a palindrome reversed string does not matter.
 */
bool isPalindrome(long long sum) {

    int  i = 0;

    // Convert integer to String.
    while(sum) {
        resultString[i++] = sum % 10;
        sum /= 10;
    }

    // Check if the String is palindrome.
    for(int j = 0, k = i - 1; j < k; ++j, --k) {
        if(resultString[j] != resultString[k])
            return false;
    }

    return true;
}


int main() {

    long long input;
    unsigned times, iterations;

    scanf("%u", &times);

    while( times-- ) {

        scanf("%lld", &input);

        iterations = 0;


        while( true ) {
            // Add input with reversed of the input.
            input += reverseNumber(input);
            ++iterations;

            // Check if the sum is palindrome then print and break.
            if( isPalindrome(input) ){
                printf("%u %lld\n", iterations, input);
                break;
            }

        }

    }


    return 0;
}
Advertisements

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