# Find the smallest binary digit multiple of given number

A decimal number is called binary digit number if its digits are binary. For example, 102 is not a binary digit number and 101 is.

We are given a decimal number N, we need to find the smallest multiple of N which is binary digit number,
Examples:

```Input : N = 2
Output : 10
Explanation : 10 is a multiple of 2.
Note that 5 * 2 = 10

Input  : N = 17
Output : 11101
Explanation : 11101 is a multiple of 17.
Note that 653 * 17 = 11101
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We can solve this problem using BFS, every node of implicit graph will be a binary digit number and if number is x, then its next level node will be x0 and x1 (x concatenated with 0 and 1).
In starting we will push 1 into our queue, which will push 10 and 11 into queue later and so on, after taking number from queue we’ll check whether this number is multiple of given number or not, if yes then return this number as result, this will be our final result because BFS proceeds level by level so first answer we got will be our smallest answer also.
In below code binary digit number is treated as string, because for some number it can be very large and can outside the limit of even long long, mod operation on number stored as string is also implemented.
Main optimization tweak of code is using a set for modular value, if a string with same mod value is previously occurred we won’t push this new string into our queue. Reason for not pushing new string is explained below,
Let x and y be strings, which gives same modular value. Let x be the smaller one. let z be another string which when appended to y gives us a number divisible by N. If so, then we can also append this string to x, which is smaller than y, and still get a number divisible by n. So we can safely ignore y, as the smallest result will be obtained via x only.

## C++

 `// C++ code to get the smallest multiple of N with ` `// binary digits only. ` `#include ` `using` `namespace` `std; ` ` `  `// Method return true if N has only 1s and 0s in its ` `// decimal representation ` `bool` `isBinaryNum(``int` `N) ` `{ ` `    ``while` `(N > 0) ` `    ``{ ` `        ``int` `digit = N % 10; ` `        ``if` `(digit != 0 && digit != 1) ` `            ``return` `false``; ` `        ``N /= 10; ` `    ``} ` `    ``return` `true``; ` `} ` ` `  `// Method return t % N, where t is stored as ` `// a string ` `int` `mod(string t, ``int` `N) ` `{ ` `    ``int` `r = 0; ` `    ``for` `(``int` `i = 0; i < t.length(); i++) ` `    ``{ ` `        ``r = r * 10 + (t[i] - ``'0'``); ` `        ``r %= N; ` `    ``} ` `    ``return` `r; ` `} ` ` `  `// method returns smallest multiple which has ` `// binary digits ` `string getMinimumMultipleOfBinaryDigit(``int` `N) ` `{ ` `    ``queue q; ` `    ``set<``int``> visit; ` ` `  `    ``string t = ``"1"``; ` ` `  `    ``//  In starting push 1 into our queue ` `    ``q.push(t); ` ` `  `    ``//  loop untill queue is not empty ` `    ``while` `(!q.empty()) ` `    ``{ ` `        ``// Take the front number from queue. ` `        ``t = q.front();      q.pop(); ` ` `  `        ``// Find remainder of t with respect to N. ` `        ``int` `rem = mod(t, N); ` ` `  `        ``// if remainder is 0 then we have ` `        ``// found our solution ` `        ``if` `(rem == 0) ` `            ``return` `t; ` ` `  `        ``// If this remainder is not previously seen, ` `        ``// then push t0 and t1 in our queue ` `        ``else` `if``(visit.find(rem) == visit.end()) ` `        ``{ ` `            ``visit.insert(rem); ` `            ``q.push(t + ``"0"``); ` `            ``q.push(t + ``"1"``); ` `        ``} ` `    ``} ` `} ` ` `  `//  Driver code to test above methods ` `int` `main() ` `{ ` `    ``int` `N = 12; ` `    ``cout << getMinimumMultipleOfBinaryDigit(N); ` `    ``return` `0; ` `} `

## Python3

 `# python code to get the  ` `# smallest multiple of N  ` `# with binary digits only ` `def` `multiple(A): ` `    ``flag ``=` `False` `    ``i ``=` `1` `    ``while``(flag !``=` `True``): ` `         `  `        ``# s = str(A) ` `        ``# print(s) ` `        ``# print(A) ` `        ``result ``=` `A ``*` `i ` `         `  `        ``# method returns smallest  ` `        ``# multiple which has ` `        ``# binary digits ` `        ``allowed_chars ``=` `set``(``'01'``) ` `        ``validationString ``=` `str``(result) ` `        ``if` `set``(validationString).issubset(allowed_chars): ` `            ``flag ``=` `True``; ` `            ``break``; ` `        ``else``: ` `            ``i ``=` `i ``+` `1` `             `  `    ``return` `validationString ` ` `  `# Driver code ` `n ``=` `12` `print``(multiple(n)) ` ` `  `# This code is contributed ` `# by HARDY_123 `

/div>

Output:

```11100
```

## tags:

Graph BFS Graph BFS