Problem statement

https://leetcode.com/problems/integer-to-english-words/

Solution

There is a lot of border cases here, basic idea is to use recursion, when we have number like 123 456 789 we need to say it is 123 Million + func(456 789) (note that we do not need plurals here which help us a lot).

Complexity

It is O(n), where n is lenght of answer, because we run recursion at most 3 times.

Code

class Solution:
    def numberToWords(self, num):
        d1 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"]
        d1 += ["Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        d2 = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        d3 = ["", "Thousand", "Million", "Billion"]
        
        def helper(num):
            if num == 0: return ""
            if num < 20: return d1[num] + " "
            if num < 100: return d2[num//10] + " " + helper(num%10)
            return d1[num//100] + " Hundred " + helper(num % 100)
        
        ans, i = "", 0
        
        while num:
            num, res = divmod(num, 1000)
            if res != 0: ans = helper(res) + d3[i] + " " + ans
            i += 1
            
        return ans.strip() or "Zero"