Can be solved also using BFS reducing the number of states to MOD only :).
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Multiples { static int MOD; static int[][] dp; static int[][] choice; public static int go(int i, int mod) { if (mod == 0) return i; else if (i > 100) return 1 << 25; else if (dp[i][mod] != -1) return dp[i][mod]; int a = go(i + 1, (mod * 10 + 1) % MOD); int b = go(i + 1, (mod * 10 + 0) % MOD); if (a <= b) choice[i][mod] = 1; else choice[i][mod] = 0; return dp[i][mod] = (a < b) ? a : b; } public static void main(String[] args) throws Exception { InputReader in = new InputReader(System.in); while (true) { MOD = in.nextInt(); if (MOD == 0) break; dp = new int[101][MOD]; choice = new int[101][MOD]; for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1); go(1, 1 % MOD); String res = "1"; int i = 1; int m = 1 % MOD; while (m != 0) { res = res + choice[i][m]; m = (m * 10 + choice[i][m]) % MOD; i++; } System.out.println(res); } } static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
I want to learn java programs. Can you please share some more programs of java with me?