-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSmallestMultiple0and1.java
147 lines (130 loc) · 4.6 KB
/
SmallestMultiple0and1.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package com.crossover.demo;
import java.math.BigInteger;
import java.util.*;
public class SmallestMultiple0and1 {
public static void main(String[] args) {
System.out.println(multiple(9));
System.out.println(multiple2(9));
System.out.println(multiple3(9));
System.out.println(multiple(3));
System.out.println(multiple2(3));
System.out.println(multiple3(3));
System.out.println(multiple(5));
System.out.println(multiple2(5));
System.out.println(multiple3(5));
}
public static String multiple(int A) {
if (A == 0) return "0";
if (isNumberBinary(A)) return String.valueOf(A);
Deque<String> queue = new LinkedList<>();
Set<Integer> set = new HashSet<>();
queue.offer("1");
while (!queue.isEmpty()) {
String temp = queue.poll();
int modNum = mod(temp, A);
if (modNum == 0) {
return temp;
} else if (!set.contains(modNum)) {
queue.offer(temp + "0");
queue.offer(temp + "1");
set.add(modNum);
}
}
return "";
}
public static boolean isNumberBinary(int N) {
int mod = 0;
while (N > 0) {
mod = N % 10;
if (mod > 1) return false;
N /= 10;
}
return true;
}
private static int mod(String s, int N) {
int r = 0;
for (int i = 0; i < s.length(); i++) {
r = r * 10 + (s.charAt(i) - '0');
r %= N;
}
return r;
}
public static String multiple2(int A) {
// if (isNumberBinary(A)) return String.valueOf(A);
Set<Integer> set = new HashSet<>();
if (A == 0) return "0";
Deque<BigInteger> queue = new LinkedList<>();
queue.add(BigInteger.ONE);
BigInteger modNum;
while (!queue.isEmpty()) {
BigInteger temp = queue.poll();
modNum = temp.mod(BigInteger.valueOf(A));
if (modNum.equals(BigInteger.ZERO)) return String.valueOf(temp);
if (!set.contains(modNum.intValue())) {
queue.add(temp.multiply(BigInteger.TEN));
queue.add(temp.multiply(BigInteger.TEN).add(BigInteger.ONE));
}
}
return "";
}
public static String multiple3(int A) {
if (A == 0) return "0";
boolean[] isVisited = new boolean[A];
String result = "0";
//The queue used by BFS
Queue<Node> queue = new ArrayDeque<>();
// Add first number 1 and mark it visited
queue.add(new Node(true, 1 % A, null));
isVisited[1 % A] = true;
//The final destination node which represents the answer
Node destNode = null;
while (!queue.isEmpty()) {
Node currNode = queue.remove();
if (currNode.val == 0) {
// we have reached a valid multiple of A
destNode = currNode;
break;
} else {
// visit the next 2 neighbours
//append 0 - (currNode.val*10)
//append 1 - (currNode.val*10 + 1)
//append '0'
int val1 = (currNode.val * 10) % A;
if (!isVisited[val1]) {
queue.add(new Node(false, val1, currNode));
isVisited[val1] = true;
}
//append '1'
int val2 = val1 + 1;
if (val2 == A) {
val2 = 0;
}
if (!isVisited[val2]) {
queue.add(new Node(true, val2, currNode));
isVisited[val2] = true;
}
}
}
// trace the path from destination to source
if (destNode != null) {
StringBuilder reversRes = new StringBuilder();
Node currNode = destNode;
while (currNode != null) {
reversRes.append(currNode.isDigitOne ? '1' : '0');
currNode = currNode.prev;
}
result = reversRes.reverse().toString();
}
return result;
}
private static class Node {
private final boolean isDigitOne;
public final int val;
public final Node prev;
public Node(boolean isDigitOne, int val, Node prev) {
this.isDigitOne = isDigitOne;
this.val = val;
this.prev = prev;
}
}
}