The problem is simple: given an integer n, find the smallest m such that n*m contains only the digits 0 and 1 in its decimal representation.
Method 1: Brute Force [Need to consider large integers, termination conditions, and time complexity]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| bool CheckNumber(int number)
{
while(number)
{
if (number%10 != 0 && number%10 != 1)
return false;
number /= 10;
}
return true;
}
int CalcMBruteForce(int n)
{
int m = 1;
while (!CheckNumber(m * n))
{
m++;
}
return m;
}
|
Method 2: BFS [Need to consider large integers, termination conditions, and duplicate elimination]
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
| int CalcM(int number)
{
int i = 1;
vector<int> vList;
vList.clear();
vList.push_back(0);
vList.push_back(1);
vector<int> vListC;
int k = 1;
// TODO:
// BigInt
// Delete duplicate
while (true)
{
vListC.clear();
for (vector<int>::size_type i = 0; i < vList.size(); i++)
{
if (vList[i] && vList[i] % number == 0)
{
return vList[i];
}
vListC.push_back(vList[i] + 0);
vListC.push_back(vList[i] + (int)pow(10.0, k));
}
vList.clear();
vList = vListC;
k++;
}
}
|