दी गई संख्या के सबसे छोटे द्विआधारी अंक एकाधिक का पता लगाएं


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना चौपाई लिंक्डइन माइक्रोसॉफ्ट स्नैपडील
पहले चौड़ाई खोजो ग्राफ

समस्या का विवरण

समस्या "दी गई संख्या के सबसे छोटे द्विआधारी अंक का पता लगाएं" बताती है कि आपको एक दशमलव संख्या N दी गई है। इसलिए N के सबसे छोटे गुणक को ढूंढें जिसमें केवल द्विआधारी अंक '0' और '1' हों।

उदाहरण

37
111

एक विस्तृत विवरण नीचे एम्बेडेड छवि में पाया जा सकता है।

दृष्टिकोण

दृष्टिकोण एक प्रदर्शन करना है वित्तीय पर्यवेक्षण बोर्ड स्ट्रिंग का उपयोग करके ट्रैवर्सल: रूट नोड के रूप में '1'। हम इस नोड में '0' और '1' को जोड़ते हैं और इसके परिणामस्वरूप '10' और '11' प्राप्त स्ट्रिंग्स को धक्का देते हैं। पंक्ति। हर बार कतार से एक स्ट्रिंग को पॉप करते हुए, हम '0' और '1' को पॉपअप स्ट्रिंग में जोड़ते हैं और परिणामी स्ट्रिंग को वापस कतार में धकेलते हैं। ट्रैवर्सल के दौरान। यदि हमें एक स्ट्रिंग मिलती है जो पूरी तरह से इनपुट नंबर को विभाजित करती है, तो हम बस इस स्ट्रिंग को वापस करते हैं।

  1. जटिलता को कम करना: हम की संख्या को कम करके हमारे दृष्टिकोण की जटिलता को कम करते हैं तार BFS ट्रैवर्सल के दौरान संसाधित। संसाधित हर स्ट्रिंग के लिए हम इसे जोड़ते हैं आधुनिक मूल्य (शेष जब संसाधित स्ट्रिंग इनपुट संख्या से विभाजित होती है) a हैश सेट। यदि किसी विशेष स्ट्रिंग के लिए, यह मॉड वैल्यू पहले से ही सेट में मौजूद है। फिर, हम BFS ट्रैवर्सल कतार में स्ट्रिंग नहीं जोड़ते हैं।
  2. कारण: जटिलता को कम करने के लिए हम उसी के तार जोड़ने से बचते हैं आधुनिक मूल्य कतार में। यह है कि अगर एक विशेष मॉड मूल्य के साथ एक स्ट्रिंग पहले से ही कतार में मौजूद है या पहले से ही संसाधित किया गया है। फिर उसी के साथ किसी भी बाद में स्ट्रिंग आधुनिक मूल्य कतार में नहीं जोड़ा गया है। इसका कारण: समान मोड मानों के साथ दो स्ट्रिंग X और Y मानें (शेष जब संसाधित स्ट्रिंग इनपुट संख्या से विभाजित होती है), X, Y की तुलना में मूल्य में छोटा होता है। Z एक और स्ट्रिंग होता है, जो Y से जोड़ा जाता है। इनपुट नंबर एन द्वारा विभाज्य एक संख्या। यदि ऐसा है, तो हम इस स्ट्रिंग को एक्स को भी जोड़ सकते हैं, और फिर भी इनपुट नंबर एन द्वारा एक नंबर विभाज्य प्राप्त कर सकते हैं। इसलिए हम सुरक्षित रूप से वाई को बीएफएस कतार में जोड़ने से बच सकते हैं।

कलन विधि

  1. के लिए एक कतार बनाएँ वित्तीय पर्यवेक्षण बोर्ड ट्रैवर्सल।
  2. बनाओ हैश सेट यह जांचने के लिए कि क्या किसी विशेष मॉड मान वाली स्ट्रिंग का सामना किया गया है या नहीं।
  3. स्रोत स्ट्रिंग '1' को कतार में धकेलने के बाद BFS ट्रैवर्सल शुरू करें।
  4. ट्रैवर्सल के दौरान:
    1. कतार से एक स्ट्रिंग पॉप।
    2. इसके लिए मॉड्यूलर मान की जाँच करें
      1. यदि मॉड्यूलर मान 0 है, तो यह विशेष स्ट्रिंग हमारी है आवश्यक उत्तर.
      2. एल्स, जांचें कि क्या सेट में मॉड्यूलर वैल्यू मौजूद है या नहीं।
  5. यदि वह मॉड्यूलर मूल्य हैश सेट में मौजूद नहीं है, तो '0' और '1' को पॉपअप स्ट्रिंग की (अलग-अलग प्रतियों) में जोड़ें।
  6. बीएफएस ट्रैवर्सल के लिए कतार में '0' और '1' को जोड़ने के बाद प्राप्त इन दो तारों को जोड़ें।
  7. इनपुट दशमलव संख्या के बाइनरी नंबर मल्टीपल पाए जाने तक चरण 4,5 और 6 को दोहराएं।

एल्गोरिथ्म नीचे दिखाया गया है:

दी गई संख्या के सबसे छोटे द्विआधारी अंक एकाधिक का पता लगाएं

कोड

C ++ कोड दी गई संख्या के सबसे छोटे बाइनरी अंक को खोजने के लिए

#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

जटिलता विश्लेषण

समय जटिलता

टी (एन) = ओ (वी + ई), समय जटिलता आवश्यक परिणाम तक पहुंचने से पहले हमारे द्वारा आने वाले तत्वों की संख्या के बराबर है।

अंतरिक्ष जटिलता

ए (एन) = ओ (वी), अंतरिक्ष जटिलता भी उसी मीट्रिक पर निर्भर है। आवश्यक परिणाम आने से पहले हम जितने तत्वों को देखते हैं।

इस प्रकार यह पता लगाना मुश्किल है कि आवश्यक परिणाम तक पहुंचने से पहले कितने नोड्स ग्राफ में मौजूद होने वाले हैं।

V = नोड्स की संख्या

ग्राफ में ई = किनारों