Project Euler : Problem 17 - Number letter counts

Problem Statement : Number letter counts

Problem 17 : If the numbers $1$ to $5$ are written out in words: one, two, three, four, five, then there are $3 + 3 + 5 + 4 + 4 = 19$ letters used in total.

If all the numbers from $1$ to $1000$ (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, $342$ (three hundred and forty-two) contains $23$ letters and $115$ (one hundred and fifteen) contains $20$ letters. The use of “and” when writing out numbers is in compliance with British usage.

Concept and Theory

This is a fairly easy problem. I will simply give you the solution.

Code

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static HashMap<Long, String> words = new HashMap<>();

	public static final long N = 1000L;

	public static void buildTable() {
		words.put(0L, "Zero");
		words.put(1L, "One");
		words.put(2L, "Two");
		words.put(3L, "Three");
		words.put(4L, "Four");
		words.put(5L, "Five");
		words.put(6L, "Six");
		words.put(7L, "Seven");
		words.put(8L, "Eight");
		words.put(9L, "Nine");
		words.put(10L, "Ten");
		words.put(11L, "Eleven");
		words.put(12L, "Twelve");
		words.put(13L, "Thirteen");
		words.put(14L, "Fourteen");
		words.put(15L, "Fifteen");
		words.put(16L, "Sixteen");
		words.put(17L, "Seventeen");
		words.put(18L, "Eighteen");
		words.put(19L, "Nineteen");
		words.put(20L, "Twenty");
		words.put(30L, "Thirty");
		words.put(40L, "Forty");
		words.put(50L, "Fifty");
		words.put(60L, "Sixty");
		words.put(70L, "Seventy");
		words.put(80L, "Eighty");
		words.put(90L, "Ninety");
		words.put(100L, "Hundred");
		words.put(1000L, "Thousand");
		words.put(1000000L, "Million");
		words.put(1000000000L, "Billion");
		words.put(1000000000000L, "Trillion");
		words.put(1000000000000000L, "Quadrillion");
		words.put(1000000000000000000L, "Quintillion");
	}

	public static String convert(int n) {
		StringBuilder sb = new StringBuilder("");
		long h = n / 100;
		n = n % 100;
		long t = n / 10;
		n = n % 10;
		long o = n;

		if (h > 0) {
			sb.append(words.get(h));
			sb.append(" ");
			sb.append(words.get(100L));
			sb.append(" ");
		}

		if (10 * t + o > 20) {
			sb.append(words.get(10 * t));
			sb.append(" ");
			if (o > 0) {
				sb.append(words.get(o));
				sb.append(" ");
			}
		} else if (10 * t + o > 0) {
			sb.append(words.get(10 * t + o));
			sb.append(" ");
		}

		return sb.toString();
	}

	public static String driver(long num) {
		int count = 0;
		StringBuilder sb = new StringBuilder("");
		do {
			int rem = (int) (num % N);
			num /= N;
			String res = convert(rem);
			if (count == 1 && rem != 0) {
				res += (words.get(1000L) + " ");
			} else if (count == 2 && rem != 0) {
				res += (words.get(1000000L) + " ");
			} else if (count == 3 && rem != 0) {
				res += (words.get(1000000000L) + " ");
			} else if (count == 4 && rem != 0) {
				res += (words.get(1000000000000L) + " ");
			}
			sb.insert(0, res);
			count++;
		} while (num != 0);

		return sb.toString().trim();
	}

    public static void main(String[] args) {
        buildTable();
		Scanner sc = new Scanner(System.in);
		long t = sc.nextLong();
		for (long i = 0; i < t; i++) {
			long n = sc.nextLong();
			if (n == 0) {
				System.out.println(words.get(0L));
			} else {
				System.out.println(driver(n));
			}
		}
    }
}
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as given in the above mentioned post, $main$.

References and Further Readings

• ProjectEuler