← All posts

Algorithms / Extract digits of a number from both ends

Let’s say, we have a problem that requires us to print all the digits of a number from the left to right.

A simple approach would be extracting the digits from the right to the left, storing them in an array, and printing that array in a reverse way.

$\underset{―}{PRINTDIGITS\cdot RIGHTTOLEFT(n)}$
$1:digits\leftarrow \text{empty list}$
$2:\mathbf{\text{while}}n>0$
$3:d\leftarrow n\text{mod}10$
$4:n\leftarrow n÷10$
$5:\mathbf{\text{push}}d\to digits$
$6:i:=lengthofdigits$
$7:\mathbf{\text{while}}i\ge 0$
$8:i\leftarrow i-1$
$9:\mathbf{\text{print}}digits[i]$

The time complexity of this algorithm would be $O(n)$, with $n$ being the number of digits in the input number. Since we need to allocate a new array, the algorithm would take $O(n)$ space as well.

To optimize the space complexity of the above algorithm, we can extract the digits from the left to the right.

We can see that, for a number $n$ of $k$ digits, if we divide $n$ by ${10}^{k-1}$, the result is the first digit of $n$, for example, with $n=54321$, there are $k=5$ digits:

$$54321÷{10}^4=5$$

And the remainder of the above calculation is actually the number $n$ without its first digit!

$$54321\text{mod}{10}^4=4321$$

We already know how to count the digits of a number, it can be obtained by:

$$k=lo{g}_{10}(n)+1$$

So, the algorithm to extract the digits from the left to the right would be:

$\underset{―}{PRINTDIGITS\cdot LEFTTORIGHT(n)}$
$1:k\leftarrow lo{g}_{10}(n)+1$
$2:\mathbf{\text{while}}n>0$
$3:d\leftarrow n÷{10}^{k-1}$
$4:n\leftarrow n\text{mod}{10}^{k-1}$
$5:k\leftarrow lo{g}_{10}(n)+1$
$6:\mathbf{\text{print}}d$

The new algorithm still has $O(n)$ time complexity, but this time, it only takes $O(1)$ space.

In line 5, we can also decrease $k$ by 1 instead of recalculating the number of digits with $lo{g}_{10}(n)$.

---