Reversing the digits of an Integer Algorithm

Design an algorithm that accepts a positive integer and reverses the order of its digits.

Algorithm development

Digit reversal is a technique that is sometimes used in computing to remove bias from a set of numbers. It is important in some fast information'-retrieval algorithms. A specific example clearly defines the relationship of the input to the desired output. For example,

                                                            Input: 27953

                                                            Output: 35972

The number 27953 is actually

2 * 10^4 + 7 * 10^3 + 9 * 10^2 + 5 * 10^1 + 3 * 10^0

To access the individual digits it is probably going to be easiest to start at one end of the number and work through to the other end. Because other than visually it is not easy to tell how many digits there are in the input number it will be best to try to establish the identity of the least significant digit (i.e. the rightmost digit). To do this we need to effectively "chop off" the least significant digit in the number. In other words we want to end up with 2795 with the 3 removed and identified.

The number 2795 can be obtained by integer division of the original number by 10 i.e. 27953 div 10->2795 This chops off the 3 but does not save it. However, 3 is the remainder that results from dividing 27953 by 10. To get this remainder use the mod function. That is,

                                                27953 mod 10->3

Applying the following two steps

            r := n mod 10  (l)=>(r = 3)

            n := n div 10    (2)=>(n = 2795)

the digit 3 is obtained and the new number 2795. Applying the same two steps to the new value of n we can obtain the 5 digit. Iteratively access the individual digits of the input number. Next major concern is to carry out the digit reversal. Applying digit extraction procedure to the first two digits  3 and then 5 are obtained. In the final output they appear as:

3 followed by 5

If the original number was 53 then we could obtain its reverse by first extracting the 3, multiplying it by 10, and then adding 5 to give 35. That is

                                                                        3x 10+5->35

The last three digits of the input number are 953. They appear in the "reversed" number as 359. Therefore at the stage when we have the 35 and then extract the 9 we can obtain the sequence 359 by multiplying 35 by 10 and adding 9. That is,

35 * 10 +9 -> 359

359 * 10 + 7 -> 3597

3597 * 10 + 2  ->  35972

The last number obtained from the multiplication and addition process Is the "digit-reversed" integer we have been seeking. On closely examining the digit extraction, and the reversal process, it is evident that they both involve a set of steps that can be performed iteratively.

            We must now find a mechanism for building up the "reversed" integer digit by digit. Let us assume that the variable dreverse is to be used to build the reversed integer. At each stage in building the reversed integer its previous value is used in conjunction with the most recently extracted digit. Rewriting the multiplication and addition process we have just described in terms of the variable dreverse,

Therefore to build the reversed integer we can use the construct:

            dreverse := (previous value of dreverse)* 10 + (most recently extracted rightmost digit)

The variable dreverse can be used on both sides of this expression. For the value of dreverse to be correct (i.e. dreverse = 3) after the first iteration it must initially be zero. This initialization step for dreverse is also needed to ensure that the algorithm functions correctly when the input number to be reversed is zero. Under what conditions should the iterative process terminate is to be found. The termination condition must in some way be related to the number of digits in the input integer. In fact as soon as all digits have been extracted and processed termination should apply. With each iteration the number of digits in the number being reversed is reduced by one, yielding the sequence shown in Table 2.1. Accumulative integer division of the "number being reversed" by 10 produces the sequence 27953, 95,279, ... . In our example, when the integer division process is applied for 5thtime a zero results since 2 is less than 10. Since at this point in the computation the "reversed" number has been fully constructed we can use the zero result to terminate the iterative process.

The central steps in our digit reversal algorithm are: 1. While there are still digits in the number being reversed do (a) extract the right most digit from the number being reversed and append this digit to the right-hand end of the current reversed number representation; (b) remove the rightmost digit from the number being reversed.

Algorithm description

1. Establish n, the positive integer to be reversed.

2. Set the initial condition for the reversed integer dreverse.

3. While the integer being reversed is greater than zero do

(a) use the remainder function to extract the rightmost digit of the 11 number being reversed; .

(b) increase the previous reversed integer representation dreverse by a factor of 10and add to it the most recently extracted digit to give the current dreverse value; .

(c) use integer division by 10 to remove the rightmost digit from the number being reversed.

This algorithm is most suitably implemented as a function which accepts as input the integer to be reversed and returns as output the integer with its digits reversed.