Broken Calculator

Given a calculator with some of the buttons broken and can only perform multiply operation, you are asked to return the minimum number of clicks you need to perform. This is a typical dynamic programming problem. Let $DP[n]$ is the minimum number of clicks to achieve $n$, then we have:

$$DP[n] = \min \{DP[k] + DP[n/k] + 1\}$$

Where $n$ can be perfectly divided by $k$. This formular is good enough for small case, as to pass the large test cases which $n$ can be $10^6$, we have to optimize the time cost. An obvious way is to apply similar techniques of prime sieve algorithm. If it is possible to achieve $i$, then when we meet $DP[i]$, we can update $DP[i\cdot 2], DP[i\cdot 3],\cdots, DP[i\cdot j]$ where $i\cdot j\le n$. The time cost after this optimization will be proportional to $n\log n$, so the problem becomes feasible.

import java.io.*;
import java.util.*;

public class BrokenCalculator {
    static private int[] C = new int[1000010];
    private static int countForNum(int num, int bit) {
        int count = 0;
        do {
            if (((bit >> (num % 10)) & 1) == 0) return Integer.MAX_VALUE;
            count++;
            num /= 10;
        } while (num > 0);
        return count;
    }
    private static String solve(int N, int bit) {
        for (int i = 0; i <= N; i++) {
            C[i] = countForNum(i, bit);
        }

        for (int i = 1; i < N; i++) {
            if (C[i] == Integer.MAX_VALUE) continue;

            for (int j = 2; (i * (long)j) <= N; j++) {
                if (C[j] == Integer.MAX_VALUE) continue;
                C[i * j] = Math.min(C[i * j], C[i] + C[j] + 1);
            }
        }

        if (C[N] == Integer.MAX_VALUE) return "Impossible";
        else return String.valueOf(C[N] + 1);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int bit = 0;
            for (int i = 0; i < 10; i++) {
                bit |= (in.nextInt() << i);
            }
            int N = in.nextInt();
            System.out.printf("Case #%d: %s\n", t + 1, solve(N, bit));
        }
    }
}