In today’s blog, we will discuss a problem where our task would be to find the Smallest Binary Digit Multiple of a given number. We are going to discuss the proper approach to this problem using BFS (Breadth First Search) along with its implementation. Furthermore, we will also be discussing the time and space complexity.

So without any further ado, let’s dig deep into the problem.

Problem Statement

The problem is to “Find the smallest binary digit multiple of the given number”. It states that if you are given a decimal number say, ‘N’ as input, find the smallest multiple of N such that it contains only the binary digits ‘0’ and ‘1’.

For example,

Example 01
Input: N=5
Output: 10
Explanation: 10 is a multiple of 5 as 5*2=10, so 10 is the smallest binary digit multiple of 5.
Example 02
Input: 37
Output: 111
Explanation: 111 is a multiple of 37 as 37*3=111, so 111 is the smallest binary digit multiple of 37.
Example 03
Input: 25
Output: 100
Explanation: 100 is a multiple of 25 as 25*4=100, so 100 is the smallest binary digit multiple of 25.

Solution Approach

The method is to do a BFS (Breadth First Search) traversal with the string '1' as the root node.

We will append '0' and '1' to this node and push the resulting strings '10' and '11' into the queue.

We will append '0' and '1' to the popped string and push the resultant string back into the queue.

Every time we pop a string from the queue.

During the traversal, if we find a string that entirely divides the supplied integer, we just return it.

Now, since BFS (Breadth First Search) proceeds level by level, the very first answer that we will get will be our final answer as well.

Optimization of the Code

We can limit the number of strings handled during BFS traversal to lower the complexity of our technique. For each string processed, we add its mod value (the remainder after we divide the processed string by the input number) to a hash set. If this mod value already exists in the set for a specific string. The string is then not added to the BFS traversal queue.

Reason

There is a reason behind not pushing the new string into our BFS queue if another string having same mod value has already occurred, and this reason is to reduce the complexity

That is if a string with a specific mod value is already in the queue or has been processed, the new strings with the same mod value are not added to the queue.

The reason can be understood with an assumption, for this, let us assume that strings X and Y have the same mod values, X is smaller than Y.

Let Z be another string that, when appended to Y, yields a number that is divisible by the input number N.

If this is the case, we can append this string to X and still get a number divisible by the input number N. As a result, we may avoid adding Y to the BFS queue.

Algorithm

Make a BFS traversal queue.

Create a hash set to determine whether or not a string with a specific mod value has been encountered.

Start the BFS traversal by adding the source string '1' to the queue.

After you start the traversal, 4.1. Pop a string from the queue. 4.2. Now check for the modular value of the string 4.2.1. If the modular value is 0, in that case, the same string is the answer. 4.2.2. Else, we need to check if the modular value is there in the set or not.

If the modular value does not exist in the hash set, append '0' and '1' to the (various copies of) popped string.

Add these two strings to the queue for BFS traversal after adding '0' and '1'.

Steps 4, 5 and 6 should be repeated until the smallest binary digit multiple of the input decimal number is found.

Dry Run

Starting the BFS traversal by adding the source string '1' to the queue.

As we saw, in starting, we will push 1 into our queue, which will push 10 and 11 into the queue later and so on, after taking the number from the queue we’ll check whether this number is a multiple of a given number or not, if yes then return this number as a result, this will be our final result because BFS proceeds level by level so the first answer we got will be our smallest answer also.

Mod value of a given number is found by taking the remainder after the division of that number with the input.

For example, 100 mod 7=2 as 7*14=98, so dividing 100 by 7 will leave a remainder of 2, which is exactly what we call its mod value.

If a string with a particular mod value is already present in the queue or has already been processed. Then any subsequent string with the same mod value is not added to the queue. This is depicted in the following diagram. Since the number “10” and “101” both give a mod value of 3 when divided by the input “7”, we do not proceed after we encounter the number “101”.

Explanation:

Here the input is 7.

The smallest binary digit multiple of the given number would be=1001

We reached this answer by following the BFS (Breadth First Search) approach as illustrated above. Also, when we find a mod value that is similar to the previous mod value we did not proceed in that direction

C++ Implementation

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* This function finds remainder when num is divided by N */
int mod(string num, int N)
{
int value = 0;
for(int i=0;i<num.length();i++)
{
value = 10*value + int(num[i] - '0');
value %= N;
}
return value;
}
/* This function produces the smallest binary digit multiple of given integer */
string smallestBinMul(int N)
{
queue <string> bfs_queue;
unordered_set <int> us;
// Intialising source string to 1
string num = "1";
bfs_queue.push(num);
/* BFS traversal */
while(!bfs_queue.empty())
{
string top = bfs_queue.front();
bfs_queue.pop();
int modulus = mod(top,N);
if(modulus == 0)
return top;
if(us.find(modulus) == us.end())
{
us.insert(modulus);
bfs_queue.push(top+"0");
bfs_queue.push(top+"1");
}
}
}
int main()
{
int N;
cout<<"Enter the decimal input:"<<endl;
cin>>N;
cout<<"The smallest binary digit multiple of given no. is:"<<endl;
cout<<smallestBinMul(N)<<endl;
return 0;
}

You can also try this code with Online C++ Compiler

In this section, we will analyze the space and time complexity of the approach we used for solving this problem.

Time Complexity

T(n) = O(V+E), where the time complexity is equal to the number of elements encountered before arriving at the desired outcome.

Here,

V is the number of nodes.

E is the graph's edges.

Space Complexity

The space complexity is likewise affected by the same measure, A(n) = O(V), that is the number of elements we encounter before arriving at the desired result.

As a result, determining how many nodes will be present in the network before obtaining the desired conclusion is difficult.

BFS is an abbreviation for Breadth First Search. BFS employs a queue to determine the shortest path.

What is the purpose of a HashSet?

A HashSet is typically used for high-performance operations that include a collection of unique data. HashSet's internal structure is geared for speedier searches because it contains only unique components. A single null value can be stored in a HashSet.

How to find Mod value?

When a number is divided by another number, the mod value returns the remainder. The outcome is of the same sign as the dividend.

On what metrics do we measure the performance of an algorithm?

The performance of an algorithm is measured on the basis of its time and space complexities.

What are BFS's limitations?

One disadvantage of BFS is that it is a 'blind' search, which means that when the search space is big, search performance will be poor when compared to other heuristic searches. If the search space is small, BFS will perform well. It works best when the goal state is in the upper left-hand corner of the tree.

Conclusion

So in this blog, we discussed the problem to find the smallest binary digit multiple for the given input. We saw how to use the BFS (Breadth First Search) approach for the problem and implemented the same followed by analyzing the time and space complexity of the code. We hope that you got a clear understanding of the problem and that now you are ready to give it an attempt yourself!

If you found this one interesting, explore our other Data Structures and Algorithm-related blogs as well: