Project Euler #51: Prime digit replacements

  • + 0 comments

    JAva code

    import java.io.*;
    import java.util.*;
    
    public class Solution {
    
       static int N = 7;
        static int K = 3;
        static int L = 7;
        static Map<String, List<Integer>> M = new HashMap<>();
        static int smPrime = 99999999;
    
        static void match(int num, StringBuilder regex, int dig, int howOften, int startPos) {
            char asDig = (char) (dig + '0');
            for (int i = startPos; i < N; i++) {
                if (regex.charAt(i) != asDig) {
                    continue;
                }
                if (i == 0 && asDig == '0') {
                    continue;
                }
                regex.setCharAt(i, '.');
                if (howOften == 1) {
                    List<Integer> addTo = M.computeIfAbsent(regex.toString(), k -> new ArrayList<>());
                    addTo.add(num);
                    if (addTo.size() >= L && addTo.get(0) < smPrime) {
                        smPrime = addTo.get(0);
                    }
                } else {
                    match(num, regex, dig, howOften - 1, i + 1);
                }
                regex.setCharAt(i, asDig);
            }
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            N = scanner.nextInt();
            K = scanner.nextInt();
            L = scanner.nextInt();
    
            int minNum = 1;
            for (int i = 1; i < N; i++) {
                minNum *= 10;
            }
            int maxNum = minNum * 10 - 1;
            boolean[] primes = new boolean[maxNum + 1];
            Arrays.fill(primes, true);
            primes[0] = primes[1] = false;
    
            for (int i = 2; i * i <= maxNum; i++) {
                if (primes[i]) {
                    for (int j = 2 * i; j <= maxNum; j += i) {
                        primes[j] = false;
                    }
                }
            }
    
            for (int i = minNum; i <= maxNum; i++) {
                if (primes[i]) {
                    String strNum = Integer.toString(i);
                    for (int dig = 0; dig <= 9; dig++) {
                        match(i, new StringBuilder(strNum), dig, K, 0);
                    }
                    if (N == 7) {
                        if (K == 1 && i > 2 * Math.pow(10, 6)) {
                            break;
                        }
                        if (K == 2 && i > 3 * Math.pow(10, 6)) {
                            break;
                        }
                    }
                }
            }
    
            String mini = "";
            for (Map.Entry<String, List<Integer>> entry : M.entrySet()) {
                List<Integer> values = entry.getValue();
                if (values.size() < L) {
                    continue;
                }
                if (!values.get(0).equals(smPrime)) {
                    continue;
                }
                StringBuilder s = new StringBuilder();
                for (int i = 0; i < L; i++) {
                    s.append(values.get(i)).append(" ");
                }
                if (mini.compareTo(s.toString()) > 0 || mini.isEmpty()) {
                    mini = s.toString();
                }
            }
            System.out.println(mini);
        }
    }