Problem 33: Digit Canceling Fractions
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s. We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
The Catch
How to speed up the current search range (90 * 90 = 8,100 iterations) and avoid trivial cases.
The Light
While looping, skip numbers that are divisible by 10 because they are trivial cases.
Given ab/cd, where a, b are digits of the numerator and c, d are digits of the denominator (a and b < c and d), ab/cd can only be a curious fraction under one of these four circumstances:
a = c
a = d
b = c
b = d
After execution, 4 fractions are found: 16/64, 19/95, 26/65, 49/98. Their products = 387296/38729600 = 1/100
The Code
public class Problem33
{
public static void main(String[] args)
{
for(double n = 10.0; n < 100.0; n++)
{
for(double d = 10.0; d < 100.0; d++)
{
String sn = Double.toString(n);
String sd = Double.toString(d);
if(n < d && n % 10.0 != 0.0 && d % 10.0 != 0.0)
{
double tmp = n/d;
double tmp2 = 0.0;
double tmpn = 0.0;
double tmpd = 0.0;
if(sn.charAt(0) == (sd.charAt(0)))
{
tmpn = Character.getNumericValue(sn.charAt(1));
tmpd = Character.getNumericValue(sd.charAt(1));
tmp2 = tmpn/tmpd;
if(tmp2 == tmp)
System.out.println(n + "/" + d);
continue;
}
if(sn.charAt(0) == (sd.charAt(1)))
{
tmpn = Character.getNumericValue(sn.charAt(1));
tmpd = Character.getNumericValue(sd.charAt(0));
tmp2 = tmpn/tmpd;
if(tmp2 == tmp)
System.out.println(n + "/" + d);
continue;
}
if(sn.charAt(1) == (sd.charAt(0)))
{
tmpn = Character.getNumericValue(sn.charAt(0));
tmpd = Character.getNumericValue(sd.charAt(1));
tmp2 = tmpn/tmpd;
if(tmp2 == tmp)
System.out.println(n + "/" + d);
continue;
}
if(sn.charAt(1) == (sd.charAt(1)))
{
tmpn = Character.getNumericValue(sn.charAt(0));
tmpd = Character.getNumericValue(sd.charAt(0));
tmp2 = tmpn/tmpd;
if(tmp2 == tmp)
System.out.println(n + "/" + d);
continue;
}
}
}
}
}
}