Problem statement

https://binarysearch.com/problems/Integer-to-English/

Solution

Equal to Leetcode 0273. Integer to English Words

Complexity

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

Code

class Solution:
    def solve(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"