Reverse and Add

The Problem

The "reverse and add" method is simple: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure.

For example:
195 Initial number
591
—–
786
687
—–
1473
3741
—–
5214
4125
—–
9339 Resulting palindrome

In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.

Task :
You must write a program that give the resulting palindrome and the number of iterations (additions) to compute the palindrome.

You might assume that all tests data on this problem:
– will have an answer,
– will be computable with less than 1000 iterations (additions),
– will yield a palindrome that is not greater than 4,294,967,295.

The Input

The first line will have a number N with the number of test cases, the next N lines will have a number P to compute its palindrome.

The Output

For each of the N tests you will have to write a line with the following data : minimum number of iterations (additions) to get to the palindrome and the resulting palindrome itself separated by one space.

Sample Input

3

195

265

750

Sample Output

4 9339
5 45254
3 6666

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            //Reverse and Add

            string initialNumber = "750";

            int flag = 0;

            for (int i = 0; i < 1000; i++)

            {

                initialNumber = ReturnSum(initialNumber, Reverse(initialNumber));

                if(CheckPalindrome(initialNumber))

                {

                    flag = i + 1;

                    break;

                }

            }

            if (flag != 0)

            {

                Console.WriteLine("Number of Iterations: " + flag);

                Console.WriteLine("Resulting palindrome: " + initialNumber);

            }

            else

            {

                Console.WriteLine("No palindrome has been found till 1000 iterations.");

            }

        }

        public static bool CheckPalindrome(string str)

        {

            if (str.Length > 0)

            {

                if (str == Reverse(str))

                {

                    return true;

                }

            }

            return false;

        }

        public static string Reverse(string text)

        {

            if (text == null) return null;

            char[] array = text.ToCharArray();

            Array.Reverse(array);

            return new string(array);

        }

        public static bool IsNumber(string num)

        {

            if (num.Length > 0)

            {

                for (int i = 0; i < num.Length; i++)

                {

                    if (!char.IsDigit(num[i]))

                    {

                        return false;

                    }

                }

                return true;

            }

            return false;

        }

        public static string ReturnSum(string num1, string num2)

        {

            if (IsNumber(num1) && IsNumber(num2))

            {

                int sum = 0, carry = 0, i = num1.Length – 1, j = num2.Length – 1;

                string sumStr = "";

                for (int k = 0; k < Math.Max(num1.Length, num2.Length); k++)

                {

                    if (i >= 0 && j >= 0)

                    {

                        sum = int.Parse(num1[i].ToString()) + int.Parse(num2[j].ToString()) + carry;

                        sumStr = (sum % 10).ToString() + sumStr;

                        carry = (sum – (sum % 10)) / 10;

                        i–; j–;

                    }

                    else if (i < 0)

                    {

                        sum = int.Parse(num2[j].ToString()) + carry;

                        sumStr = (sum % 10).ToString() + sumStr;

                        carry = (sum – (sum % 10)) / 10;

                        j–;

                    }

                    else

                    {

                        sum = int.Parse(num2[i].ToString()) + carry;

                        sumStr = (sum % 10).ToString() + sumStr;

                        carry = (sum – (sum % 10)) / 10;

                        i–;

                    }

                }

                if (carry != 0)

                {

                    sumStr = carry.ToString() + sumStr;

                }

                return sumStr;

            }

            return null;

        }

    }

}

 

Number of Iterations: 3
Resulting palindrome: 6666
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s