1 నుండి n వరకు బైనరీ సంఖ్యలను రూపొందించడానికి ఆసక్తికరమైన పద్ధతి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ బెల్జాబర్ మహీంద్రా కామ్వివా ServiceNow వూకర్
వెడల్పు మొదటి శోధన క్యూ

సమస్యల నివేదిక

“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”).

చెట్టులో రూట్ దశాంశ సంఖ్య 1 యొక్క బైనరీ ప్రాతినిధ్యానికి అనుగుణంగా ఉందని మనం చూడవచ్చు. రూట్ యొక్క ఎడమ బిడ్డ 2 యొక్క బైనరీ ప్రాతినిధ్యం, రూట్ యొక్క కుడి బిడ్డ 3 యొక్క బైనరీ ప్రాతినిధ్యం. అదేవిధంగా, “యొక్క ఎడమ నోడ్“ 2 ”అనేది 4 యొక్క బైనరీ ప్రాతినిధ్యం, మరియు“ 2 ”యొక్క కుడి నోడ్ 5 యొక్క బైనరీ ప్రాతినిధ్యం.

కాబట్టి 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 నుండి n వరకు బైనరీ సంఖ్యలను ఉత్పత్తి చేయడానికి ఆసక్తికరమైన పద్ధతికి 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), మేము ఇచ్చిన లక్ష్య మూలకాన్ని చేరుకునే వరకు మేము మూలకాలపై మాత్రమే ప్రయాణిస్తున్నాము. అందువలన అల్గోరిథం సమయం సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై), లక్ష్య మూలకం కంటే తక్కువగా ఉన్న మూలకాల ద్వారా మేము ప్రయాణించాము. మేము ఈ మూలకాలను క్యూలోకి నెట్టివేస్తున్నాము, అందువల్ల స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.