Project Euler #33: Digit canceling fractions

  • + 0 comments

    here is my submission in java, i have tested the code and provides correct results in almost all tests using the help from the discussions below however i failed the timeout, if anyone wants some refrence you can refer below-

    import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set;

    public class Main { public static void main(String[] args) { int n = 4; int k = 3;

        Set<String> fractions = new HashSet<>();
    
        for (int numerator = (int) Math.pow(10, n - 1); numerator < Math.pow(10, n); numerator++) {
            for (int denominator = numerator + 1; denominator < Math.pow(10, n); denominator++) {
                String numeratorString = Integer.toString(numerator);
                String denominatorString = Integer.toString(denominator);
    
                for (int i = 0; i < numeratorString.length(); i++) {
                    char numeratorChar = numeratorString.charAt(i);
                    for (int j = 0; j < denominatorString.length(); j++) {
                        char denominatorChar = denominatorString.charAt(j);
    
                        if (numeratorChar == '0' || denominatorChar == '0') {
                            continue;
                        }
    
                        if (numeratorChar == denominatorChar) {
                            String numeratorReduced = numeratorString.substring(0, i) + numeratorString.substring(i + 1);
                            String denominatorReduced = denominatorString.substring(0, j) + denominatorString.substring(j + 1);
    
                            if (denominatorReduced.equals("0")) {
                                continue;
                            }
    
                            double originalFraction = (double) numerator / denominator;
                            double reducedFraction = (double) Integer.parseInt(numeratorReduced) / Integer.parseInt(denominatorReduced);
    
                            if (originalFraction == reducedFraction) {
                                fractions.add(numerator + "," + denominator);
                            }
                        }
                    }
                }
            }
        }
    
        int numeratorSum = 0;
        int denominatorSum = 0;
    
        List<String> fractionList = new ArrayList<>(fractions);
        for (int i = 0; i < fractionList.size(); i++) {
            String[] fraction = fractionList.get(i).split(",");
            int numerator = Integer.parseInt(fraction[0]);
            int denominator = Integer.parseInt(fraction[1]);
    
            numeratorSum += numerator;
            denominatorSum += denominator;
        }
    
        System.out.println(numeratorSum + " " + denominatorSum);
    }
    

    }