patternjavaModerate
Project Euler #8 code implementation
Viewed 0 times
codeimplementationprojecteuler
Problem
Find the thirteen adjacent digits in the 1000-digit number that have
the greatest product." eg, the product of the first four adjacent
digits is 7 3 1 * 6 = 126
The code works perfectly and runtime is around 925323ns.
I had realized after posting
that finding the minimum was useless... so forgive me for that....
the greatest product." eg, the product of the first four adjacent
digits is 7 3 1 * 6 = 126
public class Java {
public static void main(String[] args) {
String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
long max = 0;
for(int i = 0 ; i max){
max = product;
}
}
System.out.println("max : " + max);
}
}The code works perfectly and runtime is around 925323ns.
I had realized after posting
that finding the minimum was useless... so forgive me for that....
Solution
The first thing you should do is clean your code up.
We should notice that
Next, we should notice that if we find a
Lastly,
Or, of course, rewrite the entire thing to one loop instead, which would be the preferred method.
I will warn you, if taken out of context the following line is dangerous:
This could definitely cause a division by 0 error if not handled properly. (It's handled properly here, but could easily be made not to be.)
Here's a link to ideone with the two tests, for comparison.
All-in-all, I hope this was helpful. :)
We should notice that
temp.charAt(k)-48 is called no less than once, and no more than twice in the for (int k...) loop. We can fix that (quite easily). Next, we should notice that if we find a
0 in our second loop, we can skip that many numbers ahead.Lastly,
aChar - 48 is bad practice. In Java you can subtract single-character literals. Instead of aChar - 48, let's do aChar - '0'. The 48 becomes a magic number, and it's just as easy to subtract the '0' instead. :)public class Java {
public static void main(String[] args) {
String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
long max = 0;
for (int i = 0; i max) {
max = product;
}
}
System.out.println("max : " + max);
}
}Or, of course, rewrite the entire thing to one loop instead, which would be the preferred method.
public class Java {
public static void main(String[] args) {
String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
long max = 0;
long runningProduct = 1;
int numbersLoaded = 0;
for (int i = 0; i max) {
max = runningProduct;
}
}
}
System.out.println("max : " + max);
}
}I will warn you, if taken out of context the following line is dangerous:
runningProduct /= temp.charAt(i - 13) - '0';This could definitely cause a division by 0 error if not handled properly. (It's handled properly here, but could easily be made not to be.)
Here's a link to ideone with the two tests, for comparison.
All-in-all, I hope this was helpful. :)
Code Snippets
public class Java {
public static void main(String[] args) {
String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
long max = 0;
for (int i = 0; i < temp.length() - 12; i++) {
int min = temp.charAt(i) - '0';
long product = 1;
for (int k = i; k < 13 + i; k++) {
int numK = temp.charAt(k) - '0';
min = Math.min(numK, min);
if (min == 0) {
product = 0;
i = k + 1; // The value at `k` is a zero, so we'll not bother processing from `i through k`.
break;
}
else {
product = product * numK;
}
}
if (product > max) {
max = product;
}
}
System.out.println("max : " + max);
}
}public class Java {
public static void main(String[] args) {
String temp = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
long max = 0;
long runningProduct = 1;
int numbersLoaded = 0;
for (int i = 0; i < temp.length(); i++) {
int numI = temp.charAt(i) - '0';
if (numI == 0) {
runningProduct = 1;
numbersLoaded = 0;
}
else {
if (numbersLoaded == 13) {
runningProduct /= temp.charAt(i - 13) - '0';
}
else {
numbersLoaded += 1;
}
runningProduct *= numI;
if (runningProduct > max) {
max = runningProduct;
}
}
}
System.out.println("max : " + max);
}
}runningProduct /= temp.charAt(i - 13) - '0';Context
StackExchange Code Review Q#101565, answer score: 12
Revisions (0)
No revisions yet.