Find the smallest binary digit multiple of given number

Difficulty Level Medium
Frequently asked in Amazon Fourkites LinkedIn Microsoft Snapdeal
Breadth First Search GraphViews 1946

Problem Statement

The problem “Find the smallest binary digit multiple of given number” states that you are given a decimal number N. So find the smallest multiple of N that contains only the binary digits ‘0’ and ‘1’.

Example

37
111

A detailed explanation can be found below in the embedded image.

Approach

The approach is to perform a BFS traversal using the string:  ‘1’ as root node. We append ‘0’ and ‘1’ to this node and push the strings obtained ’10’ and ’11’ as a result into the queue. Every time popping a string from the queue, we append ‘0’ and ‘1’ to the popped string and push the resultant string back into the queue. During traversal. If we find a string that divides completely the input number, we simply return this string.

  1. Reducing Complexity: We reduce the complexity of our approach by reducing the number of strings processed during BFS traversal. For every string processed we add it’s mod value (remainder when the processed string is divided by the input number) into a hash set. If for a particular string, this mod value is already present in the set. Then, we don’t add the string into the BFS traversal queue.
  2. Reason: To reduce complexity we avoid adding strings of same mod value into the queue. That is 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 into the queue. The reason for this: assume two string X and Y with the same mod values (remainder when the processed string is divided by the input number), X is smaller in value than Y. Let Z be another string which when appended to Y gives us a number divisible by input number N. If so, then we can also append this string to X, and still get a number divisible by input number N. So we can safely avoid adding Y to the BFS queue.

Algorithm

  1. Create a queue for BFS traversal.
  2. Create a hash set to check if a string with a particular mod value has been encountered or not.
  3. Begin the BFS traversal after pushing the source string ‘1’ into the queue.
  4. During Traversal:
    1. Pop a string from the queue.
    2. Check for it’s modular value
      1. if the modular value is 0, then this particular string is our required answer.
      2. Else, check if the modular value is present in the set or not.
  5. If that modular value is not present in the hash set, then append ‘0’ and ‘1’ to the (different copies of) popped string.
  6. Add these two strings obtained after appending ‘0’ and ‘1’ into the queue for BFS traversal.
  7. repeat steps 4,5 and 6 until a binary number multiple of the input decimal number is found.

The algorithm is depicted below:

Find the smallest binary digit multiple of given number

Code

C++ code to Find the smallest binary digit multiple of given number

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* 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;
}

/* produces smallest binary digit multiple of given integer */
string smallestBinaryMultiple(int N)
{
    queue <string> q;
    unordered_set <int> us;
    
    string num = "1";
    q.push(num);
    
    /* BFS traversal */
    while(!q.empty())
    {
        string top = q.front(); q.pop();
        
        int modulus = mod(top,N);
        
        if(modulus == 0)
        return top;
        
        if(us.find(modulus) == us.end())
        {
            us.insert(modulus);
            q.push(top+"0");
            q.push(top+"1");
        }
    }
}

int main()
{
    int N = 37;
    cout<<smallestBinaryMultiple(N)<<endl;
    return 0;
}
111

Java code to Find the smallest binary digit multiple of given number

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* finds remainder when num is divided by N */
    static int mod(StringBuffer num, int N)
    {
        int value = 0;
        for(int i=0;i<num.length();i++)
        {
            value = 10*value + num.charAt(i) - '0';
            value %= N;
        }
        
        return value;
    }
    
    /* produces smallest binary digit multiple of given integer */
    static StringBuffer smallestBinaryMultiple(int N)
    {
        Queue <StringBuffer> q = new LinkedList<>();
        HashSet <Integer> us = new HashSet<Integer>();
        
        StringBuffer num = new StringBuffer("1");
        q.add(num);
        
        /* BFS traversal */
        while(!q.isEmpty())
        {
            StringBuffer top = q.poll();
            
            int modulus = mod(top,N);
            
            if(modulus == 0)
            return top;
            
            if(!us.contains(modulus))
            {
                us.add(modulus);
                
                StringBuffer appendZero = new StringBuffer(top);
                appendZero.append('0');
                
                StringBuffer appendOne = new StringBuffer(top);
                appendOne.append('1');
                
                q.add(appendZero);
                q.add(appendOne);
            }
        }
        
        return num;
    }

  public static void main (String[] args) 
  {
      int N = 37;
        System.out.println(smallestBinaryMultiple(N));
  }
}
111

Complexity Analysis

Time Complexity

T(n) = O(V+E), The time complexity is equal to the number of elements we come across before reaching the required result.

Space Complexity

A(n) = O(V), The space complexity is also dependent on the same metric. The number of elements we come across before coming to the required result.

Thus it’s hard to figure out how many nodes are going to be present in the graph before reaching the required result.

V = number of nodes

E = edges in the graph

Translate »