273. Integer to English Words

Time: O(log n)

Space: O(log n)

Intuition

Process 3-digit groups (billions, millions, thousands, units) right to left. Each group is converted by a helper that handles hundreds, tens, and ones separately. Concatenate group strings with their magnitude labels.

Algorithm

1Define ONES=["","One","Two",...,"Nineteen"], TENS=["","","Twenty",...,"Ninety"].
2Helper(n) converts 1 - 999 to words.
3Process groups: billions=(num/1e9), millions=(num%1e9/1e6), thousands=(num%1e6/1e3), units=(num%1e3).
4For each non-zero group, prepend its words and magnitude label.

Example Walkthrough

Input: 1234567

1.1 million + 234 thousand + 567.
2."One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven".

Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Common Pitfalls

•Handle 0 -> "Zero" as a special case before the general logic.

273.cs

// Approach: Recursively break the number into groups of thousands, millions,
// and billions, handling words below 20 and tens with lookup tables.
// Time: O(log n) Space: O(log n)

public class Solution
{

    private readonly string[] belowTwenty = { "", "One", "Two", "Three", "Four",
                                               "Five", "Six", "Seven", "Eight", "Nine",
                                               "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
                                               "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" };
    private readonly string[] tens = { "", "", "Twenty", "Thirty", "Forty",
                                        "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };

    public string NumberToWords(int num)
    {
        return num == 0 ? "Zero" : Helper(num);
    }

    private string Helper(int num)
    {
        StringBuilder s = new StringBuilder();

        if (num < 20)
            s.Append(belowTwenty[num]);
        else if (num < 100)
            s.Append(tens[num / 10]).Append(" ").Append(belowTwenty[num % 10]);
        else if (num < 1000)
            s.Append(Helper(num / 100)).Append(" Hundred ").Append(Helper(num % 100));
        else if (num < 1000000)
            s.Append(Helper(num / 1000)).Append(" Thousand ").Append(Helper(num % 1000));
        else if (num < 1000000000)
            s.Append(Helper(num / 1000000)).Append(" Million ").Append(Helper(num % 1000000));
        else
            s.Append(Helper(num / 1000000000)).Append(" Billion ").Append(Helper(num % 1000000000));

        return s.ToString().Trim();
    }
}

Was this solution helpful?