Solution


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 1.234.567.890. 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 234 -> 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 10 to 19 which should be considered separately.

!?!../Documents/273_LIS.json:1000,632!?!

Complexity Analysis

  • Time complexity : . Intuitively the output is proportional to the number N of digits in the input.
  • Space complexity : since the output is just a string.

Analysis written by @liaison and @andvary