Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Smallest Multiple of N with Zeros and Ones
//'main' method must be in a class 'Rextester'. //Compiler version 1.8.0_111 import java.util.*; import java.lang.*; class Rextester { public static void main(String args[]) { Solution sol = new Solution(); System.out.println(Arrays.toString(sol.minMultiple(7))); System.out.println(Arrays.toString(sol.fastMinMultiple(7))); System.out.println(Arrays.toString(sol.minMultiple(27))); System.out.println(Arrays.toString(sol.fastMinMultiple(27))); //System.out.println(Arrays.toString(sol.minMultiple(1))); //System.out.println(Arrays.toString(sol.fastMinMultiple(1))); for (int i = 1; i < 30; i++) { long[] gold = sol.minMultiple(i); String[] test = sol.fastMinMultiple(i); if (gold[1] != Long.valueOf(test[1])) { System.out.println(Arrays.toString(gold)); System.out.println(Arrays.toString(test)); } } System.out.println("All good!"); } } class Solution { public String[] fastMinMultiple(int n) { Deque<Object[]> que = new ArrayDeque<>(); // [0] partial product (String) // [1] multiplier (String) // [2] carry (Integer) String[] res = null; que.offer(new Object[] {"", "", 0}); while (!que.isEmpty() && res == null) { for (int j = que.size(); j > 0; j--) { Object[] objs = que.poll(); String result = (String) objs[0]; String multiplier = (String) objs[1]; Integer carry = (Integer) objs[2]; //System.out.println(Arrays.toString(new String[] {result, multiplier, String.valueOf(carry)})); for (int i = 0; i <= 9; i++) { if (carry == 0 && i == 0) continue; int num = n*i + carry; if (isZeroOne(num)) { String[] potential = new String[] {String.valueOf(num) + result, String.valueOf(i) + multiplier}; if (res == null || res[1].compareTo(String.valueOf(i) + multiplier) > 0) { res = potential; } //System.out.println(Arrays.toString(potential)); } else if ((num % 10) <= 1) { que.offer(new Object[] { String.valueOf(num % 10) + result, String.valueOf(i) + multiplier, num / 10}); } } } } return res; } public long[] minMultiple(int n) { assert n > 0; long res = n, i = 1; while (res > 0) { if (isZeroOne(res)) return new long[] {res, i}; res += n; i++; } return null; } public boolean isZeroOne(long n) { while (n != 0) { long d = n % 10; if (d != 0 && d != 1) return false; n /= 10; } return true; } }
run
|
edit
|
history
|
help
0
Sort
CRUD vehicules
Ordenação de Vetores - LPI
Java: Tower of Hanoi
Account JAVA Cpa
pk3
Решето Эратосфена
Fgh
// Java Coding Challenge - 08: Reversing a Number using StringBuilder
Problem_rstring