दिलेल्या संख्येचा सर्वात लहान बायनरी अंक शोधा


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन फोरकाइट्स संलग्न मायक्रोसॉफ्ट Snapdeal
रुंदी प्रथम शोध आलेख

समस्या विधान

“दिलेल्या संख्येचा सर्वात लहान द्विआधारी अंक शोधा” या समस्येमध्ये असे म्हटले आहे की आपल्याला दशांश एन देण्यात आला आहे. म्हणूनच एनचे सर्वात लहान गुणक शोधा ज्यात फक्त बायनरी अंक '0' आणि '1' आहेत.

उदाहरण

37
111

एम्बेड केलेल्या प्रतिमेमध्ये तपशीलवार स्पष्टीकरण खाली आढळू शकते.

दृष्टीकोन

दृष्टिकोन म्हणजे एक करणे BFS रूट नोड म्हणून स्ट्रिंग: '1' वापरून ट्रॅव्हर्सल. आम्ही या नोडवर '0' आणि '1' समाविष्ट करतो आणि परिणामी '10' आणि '11' च्या स्ट्रिंगस मध्ये खेचतो. शेपूट. प्रत्येक वेळी रांगेतून एखादा स्ट्रिंग पॉप करतांना आम्ही '0' आणि '1' पॉप स्ट्रिंगमध्ये समाविष्ट करतो आणि परिणामी स्ट्रिंग पुन्हा रांगेत ढकलतो. ट्रॅव्हर्सल दरम्यान. जर आम्हाला एखादी स्ट्रिंग आढळली जी पूर्णपणे इनपुट नंबरला विभाजित करते, तर आम्ही फक्त ही स्ट्रिंग परत करतो.

  1. गुंतागुंत कमी करणे: आम्ही संख्या कमी करून आमच्या दृष्टिकोणातील जटिलता कमी करतो स्ट्रिंग्स बीएफएस ट्रव्हर्सल दरम्यान प्रक्रिया केली. प्रक्रिया केलेल्या प्रत्येक स्ट्रिंगसाठी आम्ही ते जोडू अद्ययावत मूल्य (प्रोसेसिंग स्ट्रिंग इनपुट नंबरद्वारे विभाजित केल्यावर उर्वरित) अ हॅश सेट. विशिष्ट स्ट्रिंगसाठी असल्यास, हे मॉड मूल्य सेटमध्ये आधीपासूनच विद्यमान आहे. मग आम्ही बीएफएस ट्रॅव्हर्सल रांगेत स्ट्रिंग जोडत नाही.
  2. कारण: गुंतागुंत कमी करण्यासाठी आम्ही त्याच तारांना जोडणे टाळतो अद्ययावत मूल्य रांगेत. हे असे आहे की जर एखाद्या विशिष्ट मोड मूल्याची स्ट्रिंग रांगेत आधीपासून अस्तित्वात असेल किंवा त्यावर प्रक्रिया केली गेली असेल. नंतर त्याच नंतरची कोणतीही स्ट्रिंग अद्ययावत मूल्य रांगेत जोडलेले नाही. याचे कारणः समान मोड मूल्यांसह दोन स्ट्रिंग X आणि Y समजा (प्रोसेसिंग स्ट्रिंग इनपुट संख्येने विभाजित केल्यावर उर्वरित), एक्स Y च्या तुलनेत लहान असेल. Y ला जोडले जाते तेव्हा आणखी एक स्ट्रिंग असू द्या. इनपुट क्रमांक एन द्वारे विभाजनीय संख्या. जर तसे असेल तर आपण ही स्ट्रिंग एक्स मध्ये देखील समाविष्ट करू शकतो आणि तरीही इनपुट क्रमांक एन द्वारे विभाजनीय संख्या मिळवू शकतो. म्हणून आम्ही बीएफएस रांगेत वाईला सुरक्षितपणे जोडणे टाळू शकतो.

अल्गोरिदम

  1. यासाठी रांग तयार करा BFS आडवा
  2. तयार हॅश सेट विशिष्ट मोड मूल्यासह स्ट्रिंग आली आहे किंवा नाही हे तपासण्यासाठी.
  3. रांगेत स्त्रोत स्ट्रिंग '1' ढकलल्यानंतर बीएफएस ट्रॅव्हर्सल सुरू करा.
  4. ट्रॅव्हर्सल दरम्यान:
    1. रांगेतून स्ट्रिंग पॉप करा.
    2. त्याचे मॉड्यूलर मूल्य तपासा
      1. जर मॉड्यूलर मूल्य 0 असेल तर ही विशिष्ट स्ट्रिंग आमची आहे आवश्यक उत्तर.
      2. अन्यथा, मॉड्यूलर मूल्य सेटमध्ये उपलब्ध आहे की नाही ते तपासा.
  5. हे मॉड्यूलर मूल्य हॅश सेटमध्ये नसल्यास, '0' आणि '1' पॉप स्ट्रींगमध्ये जोडा.
  6. '0' आणि '1' जोडल्यानंतर प्राप्त झालेल्या या दोन तारांना बीएफएस ट्रॅव्हर्सल रांगेत जोडा.
  7. इनपुट दशांश संख्येच्या बायनरी संख्येचा मल्टीपल सापडत नाही तोपर्यंत चरण 4,5 आणि 6 पुन्हा करा.

अल्गोरिदम खाली चित्रित केले आहे:

दिलेल्या संख्येचा सर्वात लहान बायनरी अंक शोधा

कोड

दिलेल्या संख्येतील सर्वात लहान बायनरी अंकांची बहुविध शोधण्यासाठी सी ++ कोड

#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

दिलेल्या संख्येचे सर्वात लहान बायनरी अंक एकाधिक शोधण्यासाठी जावा कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

टी (एन) = ओ (व्ही + ई), वेळेची जटिलता आवश्यक परिणामापर्यत पोहोचण्यापूर्वी आम्ही ज्या घटकांच्या संख्येवर येऊ शकतो त्या संख्येइतकीच असते.

स्पेस कॉम्प्लेक्सिटी

ए (एन) = ओ (व्ही), स्पेस जटिलता देखील समान मेट्रिकवर अवलंबून असते. आवश्यक परीणाम येण्यापूर्वी आम्ही किती घटकांची संख्या पार करतो.

अशा प्रकारे आवश्यक निकालापर्यंत पोहोचण्यापूर्वी ग्राफमध्ये किती नोड्स उपस्थित असतील हे शोधणे कठीण आहे.

व्ही = नोड्सची संख्या

आलेखामध्ये ई = कडा