<filename>interview/TuSimple/SmallestBinaryDigitMultiple.py
"""
Smallest Binary Digit Multiple
A decimal number is called a 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 a binary digit number, 

Example
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
"""

def getMinimumMultipleOfBinaryDigit(A):
    # queue for BFS
    q = []

    # set of visited remainders
    visitedRem = set([])
    t = '1'
    q.append(t)
    while q:
        t = q.pop(0)
        rem = int(t) % A
        if rem == 0:
            return t
        if rem not in visitedRem:
            visitedRem.add(rem)
            q.append(t+'0')
            q.append(t+'1')
         
 
# Driver code
n = 12
print(getMinimumMultipleOfBinaryDigit(n))

<filename>interview/TuSimple/SmallestBinaryDigitMultiple.py
"""
Smallest Binary Digit Multiple
A decimal number is called a 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 a binary digit number, 

Example
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
"""

def getMinimumMultipleOfBinaryDigit(A):
    # queue for BFS
    q = []

    # set of visited remainders
    visitedRem = set([])
    t = '1'
    q.append(t)
    while q:
        t = q.pop(0)
        rem = int(t) % A
        if rem == 0:
            return t
        if rem not in visitedRem:
            visitedRem.add(rem)
            q.append(t+'0')
            q.append(t+'1')
         
 
# Driver code
n = 12
print(getMinimumMultipleOfBinaryDigit(n))

Smallest Binary Digit Multiple A decimal number is called a 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 a binary digit number,   Example 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 # queue for BFS # set of visited remainders # Driver code