Convert Number to Words Problem in Java
The "Convert Number to Words" problem is a common programming challenge that involves converting a numeric input into its equivalent representation in words. In Java, this problem can be tackled through a systematic approach where the numeric value is broken down into its individual components, such as units, tens, and hundreds, and then translated into words accordingly.
Approach 1: Predefined Set of Words
The first approach for converting a number to words in Java utilizes a predefined set of words for numbers up to a certain limit. This approach is practical for smaller numbers and provides a clear mapping between numerical values and their corresponding word representations. The implementation involves breaking down the given number into segments, such as units, teens, tens, hundreds, thousands, millions, and billions, each with its set of word representations.
Algorithm
Step 1: Define three arrays units, teens, and tens to store word representations for single-digit numbers, numbers between 11 and 19, and multiples of 10, respectively.
Step 2: Implement a method convertToWords that serves as the entry point for the conversion process. It checks if the given number is zero and returns "Zero" in that case. Otherwise, it calls the convertToWordsHelper method.
Step 3: Implement a recursive method convertToWordsHelper that takes a long parameter number and returns the word representation for that number.
Step 4: Check the range of the number:
Step 4.1: If the number is less than 10, use the unit’s array to get the word representation. If the number is between 11 and 19, use the teens array.
Step 4.2: If the number is between 20 and 99, use the tens array and recursively call the method for the remaining digits.
Step 4.3: If the number is between 100 and 999, use the unit’s array for the hundreds place, append "Hundred," and recursively call the method for the remaining digits.
Step 4.4: If the number is between 1000 and 999,999, handle the thousands place. If the number is between 1,000,000 and 999,999,999, handle the millions place.
Step 4.5: If the number is greater than or equal to 1,000,000,000, handle the billions place. Concatenate the word representations obtained in the recursive calls.
Step 5: Implement a method getUnitName that takes an int parameter power and returns the corresponding unit name (Thousand, Million, Billion, etc.).
Step 6: In the main method, demonstrate how to use the convertToWords method by providing an example number.
Filename: NumberToWords.java
public class NumberToWords {
private static final String[] units = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
private static final String[] teens = {"", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public static String convertToWords(long number) {
if (number == 0) {
return "Zero";
}
return convertToWordsHelper(number).trim();
}
private static String convertToWordsHelper(long number) {
if (number < 10) {
return units[(int) number];
} else if (number < 20) {
return teens[(int) (number - 10)];
} else if (number < 100) {
return tens[(int) (number / 10)] + " " + convertToWordsHelper(number % 10);
} else if (number < 1000) {
return units[(int) (number / 100)] + " Hundred " + convertToWordsHelper(number % 100);
} else if (number < 1_000_000) {
return convertToWordsHelper(number / 1000) + " Thousand " + convertToWordsHelper(number % 1000);
} else if (number < 1_000_000_000) {
return convertToWordsHelper(number / 1_000_000) + " Million " + convertToWordsHelper(number % 1_000_000);
} else {
return convertToWordsHelper(number / 1_000_000_000) + " Billion " + convertToWordsHelper(number % 1_000_000_000);
}
}
public static void main(String[] args) {
long number = 23675;
System.out.println(convertToWords(number));
}
}
Output:
Twenty Three Thousand Six Hundred Seventy Five
Time Complexity
The time complexity of the provided code is O(log N), where N is the input number. The recursive algorithm processes each digit or segment of the number individually, and the depth of recursion is determined by the number of digits in the input number.
Space Complexity
The space complexity is also O(log N) due to the recursive nature of the algorithm. Each recursive call adds a new stack frame, and the maximum depth of the recursion is determined by the number of digits in the input number.
Approach 2: Dynamic Programming
In this approach, dynamic programming is utilized to convert a number to words without any predefined limit. Instead of using hardcoded arrays for specific ranges of numbers, this approach dynamically handles segments of the given number, allowing for flexibility with any size of the input. The algorithm breaks down the number into smaller segments and constructs the word representation iteratively. This dynamic approach is more scalable than the predefined set of words used in Approach 1.
Algorithm
Step 1: Create three arrays to store word representations for single digits (units), numbers between 11 and 19 (teens), and multiples of 10 (tens).
Step 2: Implement a method convertToWords that serves as the entry point for the conversion process. Check if the given number is zero and return "Zero" in that case. Otherwise, call the convertToWordsHelper method.
Step 3: Dynamic Programming: Implement a method convertToWordsHelper that takes a long parameter number and returns the word representation for that number.
Step 3.1: Initialize an empty StringBuilder to build the word representation iteratively. Iterate while the number is greater than zero.
Step 3.2: Check if the number is less than 10. If so, append the word representation from the unit’s array.
Step 3.3: If the number is between 11 and 19, append the word representation from the teens array. If the number is greater than or equal to 20, append the word representation from the tens array and update the number.
Step 4: Append the unit’s name (Thousand, Million, Billion, etc.) based on the power of 1000. Update the number by dividing it by 1000. Return the word representation obtained.
Step 5: In the main method, demonstrate how to use the convertToWords method by providing an example number.
Filename: NumberToWordsDynamic.java
public class NumberToWordsDynamic {
private static final String[] units = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
private static final String[] teens = {"", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public static String convertToWords(long number) {
if (number == 0) {
return "Zero";
}
return convertToWordsHelper(number).trim();
}
private static String convertToWordsHelper(long number) {
if (number == 0) {
return "";
}
StringBuilder result = new StringBuilder();
int power = 0;
while (number > 0) {
if (number % 1000 != 0) {
String segmentWords = convertSegmentToWords((int) (number % 1000));
result.insert(0, segmentWords + getUnitName(power) + " ");
}
number /= 1000;
power++;
}
return result.toString();
}
private static String convertSegmentToWords(int number) {
StringBuilder segmentWords = new StringBuilder();
if (number % 100 < 10) {
segmentWords.append(units[number % 100]);
} else if (number % 100 < 20) {
segmentWords.append(teens[number % 10]);
} else {
segmentWords.append(tens[number % 100 / 10]).append(" ").append(units[number % 10]);
}
if (number >= 100) {
segmentWords.insert(0, units[number / 100] + " Hundred ");
}
return segmentWords.toString();
}
private static String getUnitName(int power) {
switch (power) {
case 1:
return "Thousand ";
case 2:
return "Million ";
case 3:
return "Billion ";
// Add more cases as needed for higher powers
default:
return "";
}
}
public static void main(String[] args) {
long number = 27419;
System.out.println(convertToWords(number));
}
}
Output:
Twenty Seven Thousand Four Hundred Nineteen
Time Complexity
The time complexity of the provided code is O(log N), where N is the input number. The algorithm iterates through the digits of the input number, and the number of iterations is determined by the logarithm (base 10) of the input number. The primary loop in the convertToWordsHelper method iterates while the number is greater than zero, and in each iteration, the number is divided by 1000.
Space Complexity
The space complexity of the provided code is O(log N) due to the recursive nature of the algorithm and the space used by the StringBuilder. Each recursive call adds a new stack frame, and the maximum depth of the recursion is determined by the number of digits in the input number.
Approach 3: Using HashMap
In this approach, a HashMap is used to store the mapping between numerical values and their corresponding word representations. This approach allows for a flexible and extensible solution, as the word representations can be dynamically added or modified. The code defines a mapping for single digits, tens, hundreds, and powers of 1000, and uses the HashMap to look up the word representations during the conversion process.
Algorithm
Step 1: Create a HashMap named numberWords to store the mapping between numerical values and their word representations.
Step 2: Populate the numberWords HashMap with word representations for single digits, tens, hundreds, and powers of 1000.
Step 3: If the input number is zero, return "Zero." Otherwise, call the convertToWordsHelper method with the given number.
Step 4: If the number is less than or equal to 20, directly look up its word representation from the numberWords HashMap.
Step 5: If the number is less than 100, decompose it into tens and ones. Recursively call convertToWordsHelper for the tens and ones, concatenating the results.
Step 6: If the number is less than 1000, decompose it into hundreds, tens, and ones. Recursively call convertToWordsHelper for each part and concatenate the results with the appropriate units (Hundred, Thousand, etc.).
Step 7: For numbers greater than or equal to 1000, iterate over powers of 1000 (up to quadrillions). Decompose the number into segments based on the current power of 1000. Recursively call convertToWordsHelper for each segment, concatenate the results with the corresponding unit name, and break the loop.
Step 8: In the main method, demonstrate how to use the convertToWords method with an example number and getUnitName method is used to return the corresponding unit name (Thousand, Million, Billion, etc.).
Filename: NumberToWordsHashMap.java
import java.util.HashMap;
import java.util.Map;
public class NumberToWordsHashMap {
private static final Map<Integer, String> numberWords = new HashMap<>();
static {
initializeNumberWords();
}
private static void initializeNumberWords() {
numberWords.put(0, "Zero");
numberWords.put(1, "One");
numberWords.put(2, "Two");
numberWords.put(3, "Three");
numberWords.put(4, "Four");
numberWords.put(5, "Five");
numberWords.put(6, "Six");
numberWords.put(7, "Seven");
numberWords.put(8, "Eight");
numberWords.put(9, "Nine");
numberWords.put(10, "Ten");
numberWords.put(11, "Eleven");
numberWords.put(12, "Twelve");
numberWords.put(13, "Thirteen");
numberWords.put(14, "Fourteen");
numberWords.put(15, "Fifteen");
numberWords.put(16, "Sixteen");
numberWords.put(17, "Seventeen");
numberWords.put(18, "Eighteen");
numberWords.put(19, "Nineteen");
numberWords.put(20, "Twenty");
numberWords.put(30, "Thirty");
numberWords.put(40, "Forty");
numberWords.put(50, "Fifty");
numberWords.put(60, "Sixty");
numberWords.put(70, "Seventy");
numberWords.put(80, "Eighty");
numberWords.put(90, "Ninety");
}
public static String convertToWords(long number) {
if (number == 0) {
return "Zero";
}
return convertToWordsHelper(number).trim();
}
private static String convertToWordsHelper(long number) {
if (number <= 20) {
return numberWords.get((int) number);
} else if (number < 100) {
int remainder = (int) (number % 10);
return numberWords.get((int) (number / 10) * 10) + " " + convertToWordsHelper(remainder);
} else if (number < 1000) {
int remainder = (int) (number % 100);
return numberWords.get((int) (number / 100)) + " Hundred " + convertToWordsHelper(remainder);
} else {
int base = 1000;
for (int i = 1; i <= 4; i++) { // Handling up to quadrillions
if (number < Math.pow(base, i + 1)) {
int remainder = (int) (number % (long) Math.pow(base, i));
return convertToWordsHelper(number / (long) Math.pow(base, i)) + " " +
getUnitName(i) + " " + convertToWordsHelper(remainder);
}
}
}
return "";
}
private static String getUnitName(int power) {
switch (power) {
case 1:
return "Thousand";
case 2:
return "Million";
case 3:
return "Billion";
case 4:
return "Trillion";
// Add more cases as needed for higher powers
default:
return "";
}
}
public static void main(String[] args) {
long number = 35829;
System.out.println(convertToWords(number));
}
}
Output:
Thirty Five Thousand Eight Hundred Twenty Nine
Time Complexity
The time complexity of the provided code is O(log N), where N is the input number. The recursive algorithm processes each digit or segment of the number individually, and the depth of recursion is determined by the number of digits in the input number.
Space Complexity
The space complexity is O(log N) due to the recursive nature of the algorithm. Each recursive call adds a new stack frame, and the maximum depth of the recursion is determined by the number of digits in the input number. Additionally, the space complexity is influenced by the size of the HashMap (numberWords), which stores the word representations for various numerical values.
Approach 4: Using Linked List
In this approach, the idea is to represent the given number as a linked list, where each node in the list corresponds to a segment of the number. The segments are created by breaking down the original number into groups of three digits. Each segment is then processed separately, and the results are concatenated to form the final word representation of the entire number.
Algorithm
Step 1: Define a ListNode class to represent each node in the linked list. Each node stores a segment value and a reference to the next node in the list.
Step 2: Linked List Building (buildLinkedList): Create a method to build a linked list from the given number. Iterate through the number, breaking it down into segments of three digits.
Step 3: Create a ListNode for each segment and link them together to form the linked list.
Step 4: Conversion Method (convertToWords): If the input number is zero, return "Zero." Otherwise, build the linked list using the buildLinkedList method.
Step 5: Conversion Helper Method (convertToWordsHelper): Iterate through the linked list, and for each node, convert the segment value to words using the convertSegmentToWords method.
Step 6: Concatenate the word representation of each segment with the corresponding unit name (Thousand, Million, etc.). Return the final word representation.
Step 7: In the main method, demonstrate how to use the convertToWords method with an example number and getUnitName is used to return the corresponding unit name (Thousand, Million, etc.).
Filename: NumberToWordsLinkedList.java
public class NumberToWordsLinkedList {
private static final String[] units = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
private static final String[] teens = {"", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
static class ListNode {
int value;
ListNode next;
public ListNode(int value) {
this.value = value;
this.next = null;
}
}
public static String convertToWords(long number) {
if (number == 0) {
return "Zero";
}
ListNode head = buildLinkedList(number);
return convertToWordsHelper(head).trim();
}
private static ListNode buildLinkedList(long number) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (number > 0) {
int segment = (int) (number % 1000);
current.next = new ListNode(segment);
current = current.next;
number /= 1000;
}
return dummy.next;
}
private static String convertToWordsHelper(ListNode head) {
StringBuilder result = new StringBuilder();
int power = 0;
while (head != null) {
int segmentValue = head.value;
if (segmentValue > 0) {
String segmentWords = convertSegmentToWords(segmentValue);
result.insert(0, segmentWords + getUnitName(power) + " ");
}
head = head.next;
power++;
}
return result.toString();
}
private static String convertSegmentToWords(int number) {
StringBuilder segmentWords = new StringBuilder();
if (number % 100 < 10) {
segmentWords.append(units[number % 100]);
} else if (number % 100 < 20) {
segmentWords.append(teens[number % 10]);
} else {
segmentWords.append(tens[number % 100 / 10]).append(" ").append(units[number % 10]);
}
if (number >= 100) {
segmentWords.insert(0, units[number / 100] + " Hundred ");
}
return segmentWords.toString();
}
private static String getUnitName(int power) {
switch (power) {
case 1:
return "Thousand";
case 2:
return "Million";
case 3:
return "Billion";
// Add more cases as needed for higher powers
default:
return "";
}
}
public static void main(String[] args) {
long number = 41693;
System.out.println(convertToWords(number));
}
}
Output:
Forty One Thousand Six Hundred Ninety Three
Time Complexity
The time complexity of the provided code is O(log N), where N is the input number. The algorithm iterates through the digits of the input number, and the number of iterations is determined by the logarithm (base 10) of the input number. The primary loop in the convertToWordsHelper method iterates while the linked list is not null, and in each iteration, the linked list is traversed once.
Space Complexity
The space complexity of the provided code is O(log N) due to the recursive nature of the algorithm and the space used by the linked list. Each recursive call adds a new stack frame, and the maximum depth of the recursion is determined by the number of digits in the input number. Additionally, the space complexity is influenced by the size of the linked list, which represents the segments of the input number.
Conclusion
In conclusion, the problem of converting a number to words in Java can be approached in various ways, each with its own advantages and considerations. The predefined set of words approach provides a straightforward and concise solution but is limited by a predefined set of words for specific ranges. Dynamic programming allows for a more scalable and flexible solution without predefined limits. The HashMap approach enhances flexibility by dynamically mapping numerical values to their word representations. The linked list approach offers modularity and adaptability by representing segments of the number as linked list nodes. The choice of approach depends on factors such as code simplicity, scalability, and flexibility for handling different ranges of numbers.