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); } } }