6. Integer to Words.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Arrays

🚀 6. Integer to Words 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Write a function to convert a given number n into words.

The idea is to break down the number into smaller groups of three digits (hundreds, tens, and ones) according to the International Number System and convert each group into words.

🔍 Example Walkthrough:

Input:

n = 0

Output:

"Zero"

Input:

n = 123

Output:

"One Hundred Twenty Three"

Input:

n = 10245

Output:

"Ten Thousand Two Hundred Forty Five"

Input:

n = 2147483647

Output:

"Two Billion One Hundred Forty Seven Million Four Hundred Eighty Three Thousand Six Hundred Forty Seven"

Constraints:

• $0 ≤ n ≤ 231 - 1$

🎯 My Approach:

The approach follows a recursive method to convert the number into words by breaking it down into groups of three digits. Here's the breakdown:

1. Base Case for Zero:
   If the number n is 0, directly return "Zero".

2. Helper Function:
   A helper function (convertWords) is used to recursively break down the number into smaller parts. The number is split into groups of three digits starting from the least significant digits (ones, tens, hundreds).

3. Mapping of Words:

   • Numbers less than 10 (e.g., 1 to 9) are directly mapped to words like "One", "Two", etc.
   • Numbers between 10 and 19 have special names ("Ten", "Eleven", etc.).
   • Numbers between 20 and 99 are handled using the tens place (e.g., "Twenty", "Thirty") combined with the units place.
   • Numbers greater than 100 are split into hundreds, thousands, millions, billions, etc., and each group is processed recursively.

4. Recursive Breakdown:
   The number is divided into groups of three digits (using division and modulo operations), and each group is converted recursively to words. After converting each group, the corresponding scale (e.g., "Thousand", "Million") is added.

5. Return the Final Result:
   The function continues recursively until all the groups are processed, and the final result is returned by concatenating the words of each group.

🕒 Time and Auxiliary Space Complexity

• Time Complexity:
  The time complexity of the solution is O(log n) since the number is broken down into groups of three digits, and each group is processed in constant time.

• Auxiliary Space Complexity:
  The auxiliary space complexity is O(log n) due to the recursive call stack, as the number is recursively divided into smaller groups.

📝 Solution Code

Code (Cpp)

class Solution {
public:
    const vector<string> belowTen = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    const vector<string> belowTwenty = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    const vector<string> belowHundred = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

    string convertWords(int num) {
        if (num == 0) return "";
        if (num < 10) return belowTen[num];
        if (num < 20) return belowTwenty[num - 10];
        if (num < 100) return belowHundred[num / 10] + (num % 10 ? " " + convertWords(num % 10) : "");
        if (num < 1000) return convertWords(num / 100) + " Hundred" + (num % 100 ? " " + convertWords(num % 100) : "");

        if (num < 1000000) return convertWords(num / 1000) + " Thousand" + (num % 1000 ? " " + convertWords(num % 1000) : "");
        if (num < 1000000000) return convertWords(num / 1000000) + " Million" + (num % 1000000 ? " " + convertWords(num % 1000000) : "");
        return convertWords(num / 1000000000) + " Billion" + (num % 1000000000 ? " " + convertWords(num % 1000000000) : "");
    }

    string convertToWords(int n) {
        if (n == 0) return "Zero";
        return convertWords(n);
    }
};

Code (Java)

class Solution {
    private static final String[] belowTen = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    private static final String[] belowTwenty = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private static final String[] belowHundred = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    private String convertWords(int num) {
        if (num == 0) return "";
        if (num < 10) return belowTen[num];
        if (num < 20) return belowTwenty[num - 10];
        if (num < 100) return belowHundred[num / 10] + (num % 10 != 0 ? " " + convertWords(num % 10) : "");
        if (num < 1000) return convertWords(num / 100) + " Hundred" + (num % 100 != 0 ? " " + convertWords(num % 100) : "");
        if (num < 1000000) return convertWords(num / 1000) + " Thousand" + (num % 1000 != 0 ? " " + convertWords(num % 1000) : "");
        if (num < 1000000000) return convertWords(num / 1000000) + " Million" + (num % 1000000 != 0 ? " " + convertWords(num % 1000000) : "");
        return convertWords(num / 1000000000) + " Billion" + (num % 1000000000 != 0 ? " " + convertWords(num % 1000000000) : "");
    }

    public String convertToWords(int n) {
        if (n == 0) return "Zero";
        return convertWords(n);
    }
}

Code (Python)

class Solution:
    def convertToWords(self, n: int) -> str:
        belowTen = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
        belowTwenty = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        belowHundred = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]

        def convertWords(num):
            if num == 0:
                return ""
            if num < 10:
                return belowTen[num]
            if num < 20:
                return belowTwenty[num - 10]
            if num < 100:
                return belowHundred[num // 10] + ("" if num % 10 == 0 else " " + convertWords(num % 10))
            if num < 1000:
                return convertWords(num // 100) + " Hundred" + ("" if num % 100 == 0 else " " + convertWords(num % 100))
            if num < 1000000:
                return convertWords(num // 1000) + " Thousand" + ("" if num % 1000 == 0 else " " + convertWords(num % 1000))
            if num < 1000000000:
                return convertWords(num // 1000000) + " Million" + ("" if num % 1000000 == 0 else " " + convertWords(num % 1000000))
            return convertWords(num // 1000000000) + " Billion" + ("" if num % 1000000000 == 0 else " " + convertWords(num % 1000000000))

        if n == 0:
            return "Zero"
        return convertWords(n)

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count