१ देखि n सम्म बाइनरी नम्बरहरू उत्पादन गर्न चाखलाग्दो विधि


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन बेलजाबार महिन्द्रा Comviva अब सेवा वूकर
चौड़ाई पहिलो खोजी लाम

समस्या वक्तव्य

समस्या "बाइनरी नम्बरहरू १ देखि एन सम्म उत्पन्न गर्ने चाखलाग्दो विधि" ले भन्छ कि तपाईंलाई नम्बर एन दिइन्छ, १ देखि एन सम्म सबै नम्बरहरू प्रिन्ट गर्नुहोस् बाइनरी फारम.

उदाहरण

3
1 10 11

 

6
1 10 11 100 101 110

अल्गोरिदम

१ देखि एन सम्म बाइनरी नम्बरहरूको उत्पादनलाई बाइनरी रूखको रूपमा देख्न सकिन्छ, जहाँ १ रूखको जड हो र प्रत्येक नोडमा २ बच्चाहरू हुन्छन्, बाँया बच्चा स number्ख्याको अन्त्यमा '०' थपेर प्राप्त गरिन्छ जबकि दायाँ बच्चा नम्बरको अन्त्यमा '१' थप गरेर प्राप्त गरिन्छ। तल छवि हेर्नुहोस्।

१ देखि n सम्म बाइनरी नम्बरहरू उत्पादन गर्न चाखलाग्दो विधि

पहिलो एन बाइनरी नम्बरहरू उत्पन्न गर्न, एक गर्नुहोस् स्तर अर्डर ट्राभर्सल को रूख र पहिलो n नोडहरू प्रिन्ट गर्नुहोस्।

  1. Q नामको स्ट्रि ofको लाम सिर्जना गर्नुहोस्। भेरिएबल कुल ० को रूपमा आरम्भ गर्नुहोस्।
  2. "१" लाई लाममा पुश गर्नुहोस्, त्यो रूखको जड हो।
  3. जबकि कुल n भन्दा कम छ, चरण 4 र 5 दोहोर्याउनुहोस्।
  4. बाट एक तत्व पप आउट गर्नुहोस् लाम, यसलाई प्रिन्ट गर्नुहोस् र यसको बायाँ बच्चा (एलिमेन्ट + "०") र दायाँ बच्चा (एलिमेन्ट + "१") लाई लाममा धकेल्नुहोस्।
  5. १ द्वारा वृद्धि कुल।

स्पष्टीकरण

उदाहरणलाई विचार गर्नुहोस् जुन हामीले बाइनरी नम्बर १ देखि from सम्म उत्पन्न गर्नुपर्नेछ।

पहिले हामी रूखलाई माथि चित्रमा देखाइए जस्तै बनाउँदछौं, रूखको जरा १ हो, र प्रत्येक नोडको लागि यसको बायाँ बच्चा (नोड + "०" मान हुन्छ) र दायाँ बच्चा (नोड + "१" को मान) हुन्छ।

रूखमा हामी देख्न सक्छौं कि जरा दशमलव संख्या १ को बाइनरी प्रतिनिधित्वसँग मेल खान्छ। जराको बायाँ बच्चा २ को बाइनरी प्रतिनिधित्व हो, जराको दायाँ बच्चा बाइनरी प्रतिनिधित्व हो। is त्यस्तै गरी, “बायाँ नोड २ "बाइनरी प्रतिनिधित्व हो of, र दायाँ नोड" २ "बाइनरी प्रतिनिधित्व हो 1 र यस्तै।

त्यसोभए १ देखि from सम्मका नम्बरहरूको बाइनरी प्रतिनिधित्व प्रिन्ट गर्न हामीले गर्नुपर्ने भनेको रूखको पहिलो print गाँठहरू प्रिन्ट गर्नुपर्दछ, जुन स्तर क्रममा रूखलाई ट्र्यावेर कतारको प्रयोग गरेर गर्न सकिन्छ।

त्यसैले आउटपुट छ
1 10 11 100 101 110

कोड

जाभा कोड को लागी एक चाखलाग्दो विधि को लागी बाईनरी नम्बरहरु १ देखि एन सम्म उत्पन्न गर्न

import java.util.LinkedList;
import java.util.Queue;

class AnInterestingMethodToGenerateBinaryNumbersFrom1ToN {
    private static void generateBinaryNumbers(int n) {
        if (n == 0) {
            return;
        }

        // create a queue of strings
        Queue<String> q = new LinkedList<>();
        // push the root to the queue
        q.add("1");

        // initialize total as 0
        int total = 0;

        // while total is less than n
        while (total < n) {
            // remove an element from queue and print it
            String curr = q.poll();
            System.out.print(curr + " ");
            // add the left and right child of curr to the queue
            q.add(curr + "0");
            q.add(curr + "1");
            // increment total
            total++;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        int n1 = 3;
        generateBinaryNumbers(n1);

        int n2 = 6;
        generateBinaryNumbers(n2);
    }
}
1 10 11 
1 10 11 100 101 110

C ++ कोड एक चाखलाग्दो विधिमा बाइनरी नम्बरहरू १ देखि एन सम्म उत्पन्न गर्न

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

void generateBinaryNumbers(int n) {
    if (n == 0) {
        return;
    }
    
    // create a queue of strings
    queue<string> q;
    // push the root to the queue
    q.push("1");
    
    // initialize total as 0
    int total = 0;
    
    // while total is less than n
    while (total < n) {
        // remove an element from queue and print it
        string curr = q.front();
        q.pop();
        cout<<curr<<" ";
        // add the left and right child of curr to the queue
        q.push(curr + "0");
        q.push(curr + "1");
        // increment total
        total++;
    }
    
    cout<<endl;
}

int main() {
    int n1 = 3;
    generateBinaryNumbers(n1);
    
    int n2 = 6;
    generateBinaryNumbers(n2);
    
    return 0;
}
1 10 11 
1 10 11 100 101 110

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

समय जटिलता

O (N), किनकि हामी केवल दिइएका तत्वहरू मात्र ट्रान्जिंग गरिरहेका छौं जबसम्म हामी हाम्रो दिइएको लक्षित तत्वसम्म पुग्दैनौं। यसैले एल्गोरिथ्म समय मा रैखिक छ।

ठाउँ जटिलता

O (N), जस्तो कि हामीले एलिमेन्टहरूमार्फत यात्रा गरेका छौं जुन लक्ष्य तत्व भन्दा कम छन्। हामीले यी तत्वहरूलाई लाममा धकेल्दै आएका छौं त्यसैले अन्तरिक्ष जटिलता पनि रैखिक छ।