I am working on Project Euler problem 17. I am supposed to write a program that will count up the total number of characters in the numbers 1-1000 written out. You ignore whitespace and hyphens. The hundreds numbers include an 'and' (three hundred and forty-two) as dictated by the problem's instructions. My code works for the most part, except for multiples of 100, when it is counting an extra 'and'. For example, it is counting 600 as 'six hundred and'. This has led to my answer being off by 27 (3 counts for each hundred number, of which there are 9). This is the almost correct solution:
String[] nums = {"",
"one",
"two",
"three",
"four",
"five",
"six",
"seven",
"eight",
"nine",
"ten",
"eleven",
"twelve",
"thirteen",
"fourteen",
"fifteen",
"sixteen",
"seventeen",
"eighteen",
"nineteen"};
String[] ten = {"",
"",
"twenty",
"thirty",
"forty",
"fifty",
"sixty",
"seventy",
"eighty",
"ninety"};
int sum = 0;
Map<Integer, Integer> ones = new HashMap<>();
Map<Integer, Integer> teens = new HashMap<>();
Map<Integer, Integer> tens = new HashMap<>();
for (int i = 0; i < 10; i++) {
ones.put(i, nums[i].length());
}
for (int i = 10; i < nums.length; i++) {
teens.put(i, nums[i].length());
}
for (int i = 0; i < ten.length; i++) {
tens.put(i * 10, ten[i].length());
}
for (int i = 1; i < 1000; i++) {
int num = 0;
int n = i % 100;
if (n > 19 || n < 10) {
num += ones.get(n % 10);
num += tens.get(n - n % 10);
}
else {
num += teens.get(n);
}
num += i > 99 ? "hundredand".length() : 0;
num += ones.get(i / 100);
System.out.println(num + " " + i);
sum += num;
}
sum += ("onethousand").length();
// actual is 21124
System.out.println(sum);
This results in 21151 being outputted, 27 away from the expected output of 21124. The variable num is there for debugging purposes.
I tried to change one of the lines of the loop, and added in an extra statement:
num += i>99 ? "hundred".length() : 0;
num += i%100==0 ? 3 : 0;
After running this updated version, the output is 18487. I am unsure why this difference is so staggering, and would like to understand where this comes from. I first thought it was because of the ternary operator, as my knowledge about it is limited. Also, any suggestions to make the code more efficient are welcome. I was thinking to just put sum-27 before printing it out, but I felt as if that would be cheating :). Thanks!
As others have stated in their comments to your question, your problem is how your code handles numbers that are multiples of 100. You are always adding hundredand and never adding just hundred. In fact, you stated that yourself in your question:
it is counting 600 as 'six hundred and'.
In the below code, I use an explicit if statement – rather than a ternary operator – as I believe that it makes the code easier to understand when reading it. Note that that is the only change I made to your code as posted in your question.
import java.util.HashMap;
import java.util.Map;
public class MyClass {
public static void main(String args[]) {
String[] nums = {"",
"one",
"two",
"three",
"four",
"five",
"six",
"seven",
"eight",
"nine",
"ten",
"eleven",
"twelve",
"thirteen",
"fourteen",
"fifteen",
"sixteen",
"seventeen",
"eighteen",
"nineteen"};
String[] ten = {"",
"",
"twenty",
"thirty",
"forty",
"fifty",
"sixty",
"seventy",
"eighty",
"ninety"};
int sum = 0;
Map<Integer, Integer> ones = new HashMap<>();
Map<Integer, Integer> teens = new HashMap<>();
Map<Integer, Integer> tens = new HashMap<>();
for (int i = 0; i < 10; i++) {
ones.put(i, nums[i].length());
}
for (int i = 10; i < nums.length; i++) {
teens.put(i, nums[i].length());
}
for (int i = 0; i < ten.length; i++) {
tens.put(i * 10, ten[i].length());
}
for (int i = 1; i < 1000; i++) {
int num = 0;
int n = i % 100;
if (n > 19 || n < 10) {
num += ones.get(n % 10);
num += tens.get(n - n % 10);
}
else {
num += teens.get(n);
}
if (i > 99) {
num += n == 0 ? "hundred".length() : "hundredand".length();
}
num += ones.get(i / 100);
sum += num;
// System.out.printf("%2d %3d %5d%n", num, i, sum);
}
sum += ("onethousand").length();
// actual is 21124
System.out.println(sum);
}
}
When I run the above code, I get the following result:
21124
In the code in your question, you wrote (in a code comment) that this is the expected answer.