Approach 1: Divide and conquer
Let's simplify the problem by representing it as a set of simple sub-problems.
One could split the initial integer
1234567890 on the groups
containing not more than three digits
That results in representation
1 Billion 234 Million 567 Thousand 890 and
reduces the initial problem to how to convert 3-digit integer to English word.
One could split further
2 Hundred 34 into two sub-problems :
convert 1-digit integer and convert 2-digit integer. The first one is trivial.
The second one could be reduced to the first one for all 2-digit integers
but the ones from
19 which should be considered separately.
- Time complexity : .
Intuitively the output is proportional
to the number
Nof digits in the input.
- Space complexity : since the output is just a string.