fork(5) download
copy 
  1. import java.util.ArrayDeque;
  2. import java.util.Arrays;
  3. import java.util.HashSet;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6. import java.util.Set;
  7.  
  8. public class Main {
  9.     // Return the smallest multiple of the number (as a string) consisting only of digits 0 and 1
  10.     //
  11.     // All possible digits that can be constructed using the digits 0/1 can be represented
  12.     // as a tree, where at each level, appending a 0 is one branch and appending a 1 is another
  13.     //
  14.     // If we perform BFS on this tree, the first number we see which is an exact multiple of the input
  15.     // number will be the result (since it will be the smallest). Make sure to consider left
  16.     // branch (i.e. 0) before considering the right branch (i.e. 1)
  17.     //
  18.     // The 2 paths we take at each level when the current number is num:
  19.     //      (num * 10)
  20.     //      (num * 10) + 1
  21.     // 
  22.     // Since the result can grow huge quite easily, it might not be possible to store the result in a
  23.     // 32 or even a 64 bit int/long variable.
  24.     //
  25.     // One alternative is to use BigNumber, but a simpler alternative exists if we leverage modulo.
  26.     //
  27.     // The operations we perform above (i.e. multiplications and additions) will retain the useful part
  28.     // of the result when using modulo. We use the given number itself as the modulo, and when we see a
  29.     // result of 0, it means we have found a number which is an exact multiple of the input number.
  30.     //
  31.     // To reconstruct the number, we need to store the parent nodes of each node, when adding the node
  32.     // in the queue (similar to using BFS for computing shortest path)
  33.     //
  34.     // We will also need to know if we appended a 0 or a 1 at each step, and so we add this information
  35.     // as part of the node data structure as well.
  36.     //
  37.     // Re-visiting nodes is unecessary since we have seen this modulo result (i.e. value % num) already.
  38.     // Any additional digits we add from now will only make the number longer and we already are tracking
  39.     // the path for this same modulo result we've seen earlier.
  40.     //
  41.     public static String multiple(int num) {
  42.         if (num < 0) {
  43.             throw new IllegalArgumentException("Invalid args");
  44.         }
  45.  
  46.         String result = "0";
  47.  
  48.         if (num > 0) {
  49.             // An array to mark all the visited nodes
  50.             boolean[] isVisited = new boolean[num];
  51.             Arrays.fill(isVisited, false);
  52.  
  53.             // The queue used by BFS
  54.             Queue<Node> queue = new ArrayDeque<>();
  55.  
  56.             // Add the first number 1 and mark it visited
  57.             queue.add(new Node(true, 1 % num, null));
  58.             isVisited[1 % num] = true;
  59.  
  60.             // The final destination node which represents the answer
  61.             Node destNode = null;
  62.  
  63.             while (!queue.isEmpty()) {
  64.                 // Get the next node from the queue
  65.                 Node currNode = queue.remove();
  66.  
  67.                 if (currNode.val == 0) {
  68.                     // We have reached a valid multiple of num
  69.                     destNode = currNode;
  70.                     break;
  71.                 } else {
  72.                     // Visit the next 2 neighbors
  73.                     // Append 0 - (currNode.val * 10)
  74.                     // Append 1 - (currNode.val * 10) + 1
  75.  
  76.                     // Append a '0'
  77.                     int val1 = (currNode.val * 10) % num;
  78.                     if (!isVisited[val1]) {
  79.                         queue.add(new Node(false, val1, currNode));
  80.                         isVisited[val1] = true;
  81.                     }
  82.  
  83.                     // Append a '1'
  84.                     int val2 = (val1 + 1) % num;
  85.                     if (!isVisited[val2]) {
  86.                         queue.add(new Node(true, val2, currNode));
  87.                         isVisited[val2] = true;
  88.                     }
  89.                 }
  90.             }
  91.  
  92.             // Trace the path from destination to source
  93.             if (destNode == null) {
  94.                 throw new IllegalStateException("Result should not be null");
  95.             } else {
  96.                 StringBuilder reverseResultBuilder = new StringBuilder();
  97.                 Node currNode = destNode;
  98.                 while (currNode != null) {
  99.                     reverseResultBuilder.append(currNode.isDigitOne ? '1' : '0');
  100.                     currNode = currNode.parent;
  101.                 }
  102.                 result = reverseResultBuilder.reverse().toString();
  103.             }
  104.         }
  105.  
  106.         return result;
  107.     }
  108.  
  109.     // Node represents every digit being appended in the decision tree
  110.     private static class Node {
  111.         // True if '1', false otherwise (i.e. '0')
  112.         public final boolean isDigitOne;
  113.         // The number represented in the tree modulo the input number
  114.         public final int val;
  115.         // The parent node in the tree
  116.         public final Node parent;
  117.  
  118.         public Node(boolean isDigitOne, int val, Node parent) {
  119.             this.isDigitOne = isDigitOne;
  120.             this.val = val;
  121.             this.parent = parent;
  122.         }
  123.     }
  124.  
  125.     public static void main(String[] args) {
  126.         int num = new Scanner(System.in).nextInt();
  127.         System.out.println("Input number: " + num);
  128.         System.out.println("Smallest multiple using only 0s and 1s as digits: " + Main.multiple(num));
  129.     }
  130. }
  131.  
  132.  
Success #stdin #stdout 3.45s 322368KB
comments (?)
stdin
copy 
12345678
stdout
copy 
Input number: 12345678
Smallest multiple using only 0s and 1s as digits: 100010110000001110001010
https://ideone.com/2R2q34
Smallest Multiple of a number using only 0s and 1s
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!