1 से n तक बाइनरी नंबर उत्पन्न करने के लिए एक दिलचस्प विधि  


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

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

समस्या "एक दिलचस्प विधि 1 से n तक बाइनरी नंबर उत्पन्न करने के लिए" बताती है कि आपको एक नंबर n दिया गया है, 1 से n में सभी संख्याओं को प्रिंट करें बाइनरी फॉर्म.

उदाहरण  

3
1 10 11

 

6
1 10 11 100 101 110

कलन विधि  

1 से n तक की बाइनरी संख्या की पीढ़ी को एक बाइनरी ट्री के रूप में देखा जा सकता है, जहाँ 1 पेड़ की जड़ है और प्रत्येक नोड में 2 बच्चे हैं, बाएं बच्चे को नंबर के अंत में '0' जोड़कर प्राप्त किया जाता है जबकि दायां बच्चा संख्या के अंत में '1' जोड़कर प्राप्त किया जाता है। निचे इमेज देखे।

1 से n तक बाइनरी नंबर उत्पन्न करने के लिए एक दिलचस्प विधिपिन

पहले n बाइनरी नंबर जेनरेट करने के लिए a स्तर का आदेश का पेड़ और पहले n नोड्स को प्रिंट करें।

  1. Q नामक स्ट्रिंग की एक कतार बनाएँ। एक वैरिएबल कुल को 0 के रूप में प्रारंभ करें।
  2. "1" को कतार में रखें, जो पेड़ की जड़ है।
  3. जबकि कुल n से कम है, चरण 4 और 5 को दोहराएं।
  4. से एक तत्व पॉप पंक्ति, इसे प्रिंट करें और अपने बाएं बच्चे (तत्व + "0") और दाएं बच्चे (तत्व + "1") को कतार में धकेलें।
  5. 1 से वृद्धि कुल।

व्याख्या

उदाहरण पर विचार करें कि हमें 1 से 6 तक बाइनरी नंबर उत्पन्न करना है।

पहले हम पेड़ को ऊपर की छवि में दिखाए गए अनुसार बनाते हैं, पेड़ की जड़ 1 है, और प्रत्येक नोड के लिए उसका बायां बच्चा है (नोड + "0" का मूल्य) और दायां बच्चा है (नोड + "1" का मूल्य)।

यह भी देखें
अनुक्रम Leetcode समाधान से अंकगणितीय प्रगति कर सकते हैं

पेड़ में हम देख सकते हैं कि जड़ दशमलव संख्या के द्विआधारी प्रतिनिधित्व से मेल खाती है। जड़ का बायां बच्चा 1 का द्विआधारी प्रतिनिधित्व है, जड़ का दायां बच्चा 2. का द्विआधारी प्रतिनिधित्व है। इसी तरह, बाईं ओर का नोड " 3 ”2 का बाइनरी प्रतिनिधित्व है, और“ 4 ”का दायां नोड 2 और इसी तरह का बाइनरी प्रतिनिधित्व है।

तो 1 से 6 तक संख्याओं के द्विआधारी प्रतिनिधित्व को प्रिंट करने के लिए, हमें केवल इतना करना है कि पेड़ के पहले 6 नोड्स को प्रिंट करना है, जो कि स्तर क्रम में पेड़ को पीछे करके एक कतार का उपयोग करके किया जा सकता है।

इसलिए, आउटपुट है
1 10 11 100 101 110

कोड  

1 से n तक बाइनरी नंबर जेनरेट करने के लिए जावा कोड एक दिलचस्प विधि

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

सी ++ कोड 1 से एन तक बाइनरी नंबर उत्पन्न करने के लिए एक दिलचस्प विधि

#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

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

समय जटिलता

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

यह भी देखें
पहले लापता पॉजिटिव

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

पर), जैसा कि हमने उन तत्वों के माध्यम से पता लगाया है जो लक्ष्य तत्व से कम हैं। हम इन तत्वों को कतार में धकेल रहे हैं, इसलिए अंतरिक्ष की जटिलता भी रैखिक है।