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.
$\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:
$\underline{\normalsize{P}\small{RINT}\normalsize{D}\small{IGITS}\cdot\normalsize{L}\small{EFT}\normalsize{T}\small{O}\normalsize{R}\small{IGHT}(n)}$
$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)$.