04.19.2022 - Algorithms/Extract digits of a number from both ends

« All posts

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.

$\underline{\normalsize{P}\small{RINT} \normalsize{D}\small{IGITS}\cdot\normalsize{R}\small{IGHT}\normalsize{T}\small{O}\normalsize{L}\small{EFT}(n)}$
$1: \quad digits \leftarrow \text{empty list}$
$2: \quad \textbf{while} \ n \gt 0$
$3: \quad \quad d \leftarrow n \ \text{mod} \ 10$
$4: \quad \quad n \leftarrow n \div 10$
$5: \quad \quad \textbf{push}\ d\ \rightarrow \ digits$
$6: \quad i := length\ of\ digits$
$7: \quad \textbf{while} \ i \geq 0$
$8: \quad \quad i \leftarrow i - 1$
$9: \quad \quad \textbf{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 \div 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 = log_{10}(n) + 1

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

$1: \quad k \leftarrow log_{10}(n) + 1$
$2: \quad \textbf{while} \ n \gt 0$
$3: \quad \quad d \leftarrow n \div 10^{k-1}$
$4: \quad \quad n \leftarrow n\ \text{mod} \ 10^{k-1}$
$5: \quad \quad k \leftarrow log_{10}(n) + 1$
$6: \quad \quad \textbf{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 $log_{10}(n)$.

Read more