Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Smallest Multiple of N with Zeros and Ones
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//'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; } }
[
+
]
Show input
Compilation time: 0.84 sec, absolute running time: 0.85 sec, cpu time: 1.29 sec, memory peak: 20 Mb, absolute service time: 1,7 sec
edit mode
|
history
|
discussion
[1001, 143] [1001, 143] [1101111111, 40781893] [1101111111, 40781893] All good!