Solution For Integer To English Words

Problem Statement:

Convert a non-negative integer num to its English words representation.

Example 1:
Input: num = 123
Output: “One Hundred Twenty Three”

Example 2:
Input: num = 12345
Output: “Twelve Thousand Three Hundred Forty Five”

Example 3:
Input: num = 1234567
Output: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Example 4:
Input: num = 0
Output: “Zero”

Solution:

The problem is to convert a non-negative integer to its English words representation. To solve this problem, we can break it down into smaller parts and use recursion to solve it. We will create a function that takes a number and returns its English word representation.

Step 1: Create a list of strings that contains the numbers from 0 to 19 and all the multiples of ten up to 90.

num_str = [“Zero”, “One”, “Two”, “Three”, “Four”, “Five”, “Six”, “Seven”, “Eight”, “Nine”, “Ten”,
“Eleven”, “Twelve”, “Thirteen”, “Fourteen”, “Fifteen”, “Sixteen”, “Seventeen”, “Eighteen”, “Nineteen”]

tens_str = [“”, “”, “Twenty”, “Thirty”, “Forty”, “Fifty”, “Sixty”, “Seventy”, “Eighty”, “Ninety”]

Step 2: Create a function num_to_word that takes a number and returns its English word representation.

def num_to_word(n: int) -> str:
if n < 20:
return num_str[n] elif n < 100:
return tens_str[n//10] + ” ” + num_str[n%10] if n%10 != 0 else tens_str[n//10] elif n < 1000:
return num_str[n//100] + ” Hundred ” + num_to_word(n%100) if n%100 != 0 else num_str[n//100] + ” Hundred”
elif n < 1000000:
return num_to_word(n//1000) + ” Thousand ” + num_to_word(n%1000) if n%1000 != 0 else num_to_word(n//1000) + ” Thousand”
elif n < 1000000000:
return num_to_word(n//1000000) + ” Million ” + num_to_word(n%1000000) if n%1000000 != 0 else num_to_word(n//1000000) + ” Million”
else:
return num_to_word(n//1000000000) + ” Billion ” + num_to_word(n%1000000000) if n%1000000000 != 0 else num_to_word(n//1000000000) + ” Billion”

Step 3: In the main function, call the num_to_word function with the given input integer.

def numberToWords(num: int) -> str:
if num == 0:
return “Zero”
else:
return num_to_word(num)

Time Complexity:

The time complexity of the above solution is O(log n) since we are dividing the input number by 10 at each recursive call.

Space Complexity:

The space complexity of the above solution is O(1) since we are using a fixed amount of memory to store the strings. The recursive function call stack will take additional space, but it is proportional to the number of digits in the input number and therefore can be considered O(log n).

Step by Step Implementation For Integer To English Words

public class Solution {
    public String numberToWords(int num) {
        // TODO: Implement your solution here
        return null;
    }
}

def intToEnglish(num): 
    
    # create a dictionary with key as the integer  
    # and the corresponding value as the English word 
    # for that integer 
    d = {0: 'Zero', 1: 'One', 2: 'Two', 3: 'Three', 4: 'Four', 5: 'Five',  
         6: 'Six', 7: 'Seven', 8: 'Eight', 9: 'Nine', 10: 'Ten',  
        11: 'Eleven', 12: 'Twelve', 13: 'Thirteen', 14: 'Fourteen',  
        15: 'Fifteen', 16: 'Sixteen', 17: 'Seventeen', 18: 'Eighteen', 
        19: 'Nineteen', 20: 'Twenty', 30: 'Thirty', 40: 'Forty',  
        50: 'Fifty', 60: 'Sixty', 70: 'Seventy', 80: 'Eighty',  
        90: 'Ninety'} 
    
    # if the given number is less than or equal to 20, 
    # then return the corresponding English word  
    if num <= 20: 
        return d[num] 
    
    # if the given number is greater than 20, then extract  
    # the last two digits and concatenate the English words  
    # for those digits 
    if num > 20: 
        return d[num // 10 * 10] + ' ' + d[num % 10] 
    
# driver code 
  
# given number 
num = 123
  
print(intToEnglish(num))

var integerToEnglishWords = function(num) {
    
    // create a map of numbers to words
    // we will use this to convert the digits in num to their corresponding words
    let map = {
        0: 'Zero',
        1: 'One',
        2: 'Two',
        3: 'Three',
        4: 'Four',
        5: 'Five',
        6: 'Six',
        7: 'Seven',
        8: 'Eight',
        9: 'Nine',
        10: 'Ten',
        11: 'Eleven',
        12: 'Twelve',
        13: 'Thirteen',
        14: 'Fourteen',
        15: 'Fifteen',
        16: 'Sixteen',
        17: 'Seventeen',
        18: 'Eighteen',
        19: 'Nineteen',
        20: 'Twenty',
        30: 'Thirty',
        40: 'Forty',
        50: 'Fifty',
        60: 'Sixty',
        70: 'Seventy',
        80: 'Eighty',
        90: 'Ninety'
    }
    
    // if num is 0, return 'Zero'
    if (num === 0) return map[num];
    
    // we will use this array to store the words corresponding to the digits in num
    let result = [];
    
    // helper function to append a word to the result array
    let append = function(word) {
        result.push(word);
    }
    
    // helper function to convert a 2-digit number to words
    // for example, if num is 42, this function will return 'FortyTwo'
    let convertTwoDigits = function(num) {
        // if num is a single digit number, we can just look up the word in the map and return it
        if (num < 10) return map[num];
        
        // otherwise, num is a 2-digit number
        // we will first get the word for the tens place by looking up num in the map
        // for example, if num is 42, the tens place word will be 'Forty'
        let tensPlaceWord = map[Math.floor(num / 10) * 10];
        
        // then, we will get the word for the ones place by looking up the last digit of num in the map
        // for example, if num is 42, the ones place word will be 'Two'
        let onesPlaceWord = map[num % 10];
        
        // finally, we will return the concatenation of the two words
        // for example, if num is 42, we will return 'FortyTwo'
        return tensPlaceWord + onesPlaceWord;
    }
    
    // helper function to convert a 3-digit number to words
    // for example, if num is 123, this function will return 'OneHundredTwentyThree'
    let convertThreeDigits = function(num) {
        // if num is a 2-digit number, we can just convert it to words and return it
        if (num < 100) return convertTwoDigits(num);
        
        // otherwise, num is a 3-digit number
        // we will first get the word for the hundreds place by looking up the first digit of num in the map
        // for example, if num is 123, the hundreds place word will be 'One'
        let hundredsPlaceWord = map[Math.floor(num / 100)];
        
        // then, we will get the word for the last 2 digits of num by converting those digits to words
        // for example, if num is 123, the last 2 digits are 23
        // we will convert those digits to words and store the result in a variable called lastTwoDigitsWords
        let lastTwoDigitsWords = convertTwoDigits(num % 100);
        
        // finally, we will return the concatenation of the hundreds place word, 'Hundred', and the last 2 digits words
        // for example, if num is 123, we will return 'OneHundredTwentyThree'
        return hundredsPlaceWord + 'Hundred' + lastTwoDigitsWords;
    }
    
    // we will use this array to store the place values (ones, thousands, millions, etc)
    // for example, if num is 12345, the place values array will be ['One', 'Thousand', 'Million']
    let placeValues = [];
    
    // we will use this variable to keep track of the place value index while we iterate through num
    // for example, if num is 12345, the place value index will start at 0 and end at 2
    let placeValueIndex = 0;
    
    // we will use this variable to keep track of the number of digits remaining in num
    // for example, if num is 12345, the number of digits remaining will start at 5 and end at 0
    let numDigitsRemaining = num.toString().length;
    
    // we will iterate through num from right to left
    // for example, if num is 12345, we will iterate through it like this: 5 -> 4 -> 3 -> 2 -> 1
    for (let i = num; i > 0; i = Math.floor(i / 10)) {
        // we will get the last digit of i by doing a modulus operation
        // for example, if i is 12345, the last digit will be 5
        let lastDigit = i % 10;
        
        // if the last digit is non-zero, we will convert it to words and append it to the result array
        if (lastDigit !== 0) {
            // we will get the place value for the current digit by looking up the place value index in the place values array
            // for example, if the place value index is 2, the place value will be 'Million'
            let placeValue = placeValues[placeValueIndex];
            
            // we will get the word for the current digit by converting it to words
            // for example, if the current digit is 5 and the place value is 'Million', the word will be 'FiveMillion'
            let word = convertThreeDigits(lastDigit) + placeValue;
            
            // we will append the word to the result array
            append(word);
        }
        
        // if the number of digits remaining is a multiple of 3, we will update the place value index
        // for example, if the number of digits remaining is 9 (3 * 3), we will increment the place value index by 1
        if (numDigitsRemaining % 3 === 0) placeValueIndex++;
        
        // we will decrement the number of digits remaining
        numDigitsRemaining--;
    }
    
    // finally, we will return the result array joined into a string
    // for example, if num is 12345, the result array will be ['Five', 'Thousand', 'OneHundredTwentyThree']
    // we will join the result array into a string and return it
    return result.join(' ');
};

class Solution {
public:
    // Function to convert a given integer to English words 
    string numberToWords(int num) 
    { 
        // Strings to return the number in words 
        // corresponding to its digits 
        string one[] = { "", "One", "Two", "Three", "Four", 
                         "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
                         "Eleven", "Twelve", "Thirteen", "Fourteen", 
                         "Fifteen", "Sixteen", "Seventeen", "Eighteen", 
                         "Nineteen" }; 
  
        // Strings to return the number in words 
        // corresponding to the place value 
        string ten[] = { "", "", "Twenty", "Thirty", "Forty", "Fifty", 
                         "Sixty", "Seventy", "Eighty", "Ninety" }; 
  
        // If number is 0 
        if (num == 0) 
            return "Zero"; 
  
        // If number is divisible by 1000 i.e., after 
        // removing last 3 digits 
        if (num % 1000 == 0) 
            return numberToWords(num / 1000) + " Thousand"; 
  
        // If number is divisible by 100 i.e., after 
        // removing last 2 digits 
        if (num % 100 == 0) 
            return numberToWords(num / 100) + " Hundred"; 
  
        // If number is divisible by 10 i.e., after 
        // removing last digit 
        if (num % 10 == 0) 
            return numberToWords(num / 10) + " Ten"; 
  
        // If number is not divisible by 10 
        else
            return numberToWords(num / 10 * 10) + " " + 
                   one[num % 10]; 
    } 
};

using System; 

public class Solution { 

// this array is used to store the string values of the numbers from 0 - 19 
public static string[] ones = new string[]{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}; 

// this array is used to store the string values of the numbers from 20, 30, 40, ... 90 
public static string[] tens = new string[]{"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}; 

// this array is used to store the string values of the numbers from 100, 1000, 1000000, ... 
public static string[] bigs = new string[]{"", "Thousand", "Million", "Billion"}; 

// this method converts an integer value into its English word representation 
public static string convert(int n) 
{ 
if (n == 0) 
{ 
return "Zero"; 
} 

// create an empty string to store the English word representation of the integer 
string s = ""; 

// determine the number of big values (i.e. 100, 1000, 1000000, ...) in the integer 
int count = 0; 

// loop through the integer, starting with the most significant digit, and add the appropriate string values to the empty string 
while (n > 0) 
{ 
// determine the string value of the current digit 
if (n % 1000 != 0) 
{ 
s = helper(n % 1000) + bigs[count] + " " + s; 
} 

// increment the number of big values 
count++; 

// remove the most significant digit from the integer 
n /= 1000; 
} 

// return the string representation of the integer 
return s.Trim(); 
} 

// this method converts an integer value in the range [1, 999] into its English word representation 
public static string helper(int n) 
{ 
if (n == 0) 
{ 
return ""; 
} 
else if (n < 20) 
{ 
return ones[n] + " "; 
} 
else if (n < 100) 
{ 
return tens[n / 10] + " " + helper(n % 10); 
} 
else 
{ 
return ones[n / 100] + " Hundred " + helper(n % 100); 
} 
} 
}