वैकल्पिक x और y आवृत्तियों के रूप में एक बाइनरी स्ट्रिंग को पुनर्व्यवस्थित करें


कठिनाई स्तर मध्यम
में अक्सर पूछा एकोलाइट सिस्को Citrix वृद्धि आईबीएम जानकारी एज Pinterest Roblox टेस्ला
तार

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

मान लीजिए कि आपको बाइनरी दी गई है स्ट्रिंग, और दो नंबर x और y। स्ट्रिंग में 0s और 1s ही होते हैं। समस्या "बाइनरी स्ट्रिंग को वैकल्पिक x और y आवृत्तियों के रूप में पुनर्व्यवस्थित करें" स्ट्रिंग को पुनर्व्यवस्थित करने के लिए कहती है जैसे कि 0 x x 1 बार आती है ⇒ फिर से x 0 आती है x 1 ⇒ y बार आती है और इसी तरह से या तो 0s या 1 तक आती है। समाप्त हो गया है। फिर स्ट्रिंग के शेष भाग को संक्षिप्त करें और इसे प्रिंट करें।

उदाहरण

str = “01101”,

x = 1

y = 1
01011

व्याख्या

पहले 0 मुद्रित x बार, फिर 1 मुद्रित y बार, फिर 0 x बार फिर 1 y बार, लेकिन अब 0 शेष है इसलिए हम स्ट्रिंग के शेष भाग को 1 है।

वैकल्पिक x और y आवृत्तियों के रूप में एक बाइनरी स्ट्रिंग को पुनर्व्यवस्थित करें

 

वैकल्पिक x और y आवृत्तियों के रूप में एक बाइनरी स्ट्रिंग को पुनर्व्यवस्थित करने के लिए एल्गोरिदम

1. Count the total number of 0s and 1s.
2. Make a loop till the count of either of zeros or ones will be 0.
  1. Traverse in an individual loop for zeroCount, till the value x is reached and till the zeroCount will not be 0, print the 0, and decrease the value of zeroCount by 1.
  2. Traverse in an individual loop for onesCount, till the value y is reached and till the onesCount will not be 0, print the 1, and decrease the value of onesCount by 1.

व्याख्या

एक बाइनरी स्ट्रिंग इनपुट के रूप में हमने दिया है। उस बाइनरी स्ट्रिंग में 0s और 1s होते हैं जैसा कि नाम से ही पता चलता है। हमें दो मान x और y भी दिए गए हैं। ऐसा हमें आउटपुट स्ट्रिंग x में 0s और आउटपुट स्ट्रिंग “y” बार में लगातार 1s को दोहराना है। और अगर कोई स्ट्रिंग बची है तो इस आउटपुट स्ट्रिंग के साथ शेष स्ट्रिंग को मिलाएं। इसके लिए, हम शून्यकाउंट और स्वयं दोनों के लिए एक सरल काउंटर के अलावा कुछ भी उपयोग नहीं करने जा रहे हैं, दोनों शून्य और लोगों के लिए संख्या और ट्रैक रखने के लिए।

हम प्रत्येक अक्षर को स्ट्रिंग को आगे बढ़ाने जा रहे हैं। प्रत्येक अक्षर एक स्ट्रिंग के रूप में या तो 0 या 1 होगा। और हम गिनेंगे कि दिए गए तार में कितने शून्य हैं और कितने मौजूद हैं? शून्य की संख्या को शून्यकाउंट में संग्रहीत किया जाएगा और लोगों की संख्या को स्वयं में संग्रहीत किया जाएगा। ये दो चर हम संचालन करने के बाद भी शून्य और लोगों की गणना करेंगे।

एक स्ट्रिंग में शून्य और लोगों की कुल संख्या की गिनती प्राप्त करने के बाद। हम एक शर्त के साथ एक लूप शुरू करेंगे जो लूप शून्यकाउंट या अप करने के लिए जाएगा। मूल्य एक लूप में पहुंच जाता है। इस समय के दौरान हम '0' को प्रिंट करेंगे और शून्यकाउंट के मूल्य को कम करेंगे और इसे x बार प्रिंट करेंगे। और उसके बाद एक और लूप निष्पादित किया जाएगा, जो '0' y बार प्रिंट करेगा। फिर अपने आप के मूल्य को कम करते रहें। इससे बाकी तार प्रभावित नहीं होंगे और हमें वांछित आउटपुट मिलेगा।

कोड

सी ++ कोड एक बाइनरी स्ट्रिंग को वैकल्पिक एक्स और वाई घटनाओं के रूप में पुनर्व्यवस्थित करने के लिए

#include<iostream>

using namespace std;

void arrangeZeroesAndOnes(string str, int x, int y)
{
    int zeroCount = 0;
    int onesCount = 0;
    int len = str.length();

    for (int i = 0; i < len; i++)
    {
        if (str[i] == '0')
            zeroCount++;
        else
            onesCount++;
    }
    while (zeroCount > 0 || onesCount > 0)
    {
        for (int j = 0; j < x && zeroCount > 0; j++)
        {
            if (zeroCount > 0)
            {
                cout << "0";
                zeroCount--;
            }
        }
        for (int j = 0; j < y && onesCount > 0; j++)
        {
            if (onesCount > 0)
            {
                cout << "1";
                onesCount--;
            }
        }
    }
}
int main()
{
    string str = "01101";
    int x = 1;
    int y = 1;
    arrangeZeroesAndOnes(str, x, y);
    return 0;
}
01011

जावा कोड एक बाइनरी स्ट्रिंग को वैकल्पिक एक्स और वाई घटनाओं के रूप में पुनर्व्यवस्थित करने के लिए

class arrangeBinaryString
{
    static void arrangeZeroesAndOnes(String str, int x, int y)
    {
        int zeroCount = 0;
        int onesCount = 0;
        int len = str.length();

        for (int i = 0; i < len; i++)
        {
            if (str.charAt(i) == '0')
                zeroCount++;
            else
                onesCount++;
        }

        while (zeroCount > 0 || onesCount > 0)
        {
            for (int j = 0; j < x && zeroCount > 0; j++)
            {
                if (zeroCount > 0)
                {
                    System.out.print ("0");
                    zeroCount--;
                }
            }
            for (int j = 0; j < y && onesCount > 0; j++)
            {
                if (onesCount > 0)
                {
                    System.out.print("1");
                    onesCount--;
                }
            }
        }
        System.out.println();
    }
    public static void main (String[] args)
    {
        String str = "01101";
        int x = 1;
        int y = 1;
        arrangeZeroesAndOnes(str, x, y);

    }
}
01011

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

समय जटिलता

पर) जहां "N" स्ट्रिंग की लंबाई है। यहां हमने लूप को स्ट्रिंग की लंबाई के बराबर चलाया। कारण हमें एक विशेष तरीके से स्ट्रिंग को पुनर्व्यवस्थित करने की आवश्यकता थी। हमें उन सभी पात्रों को छापना पड़ा, जिन्होंने इसे रैखिक समय की जटिलता में चलाया।

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

ओ (1), क्योंकि हम नई स्ट्रिंग को स्टोर नहीं कर रहे हैं। हम केवल नए स्ट्रिंग के तत्वों को प्रिंट कर रहे हैं। इसलिए यह ऑपरेशन हमें किसी भी स्थान पर खर्च नहीं करता है। और इसलिए एल्गोरिथ्म के लिए अंतरिक्ष जटिलता स्वयं स्थिर है। जबकि पूरे प्रोग्राम को इनपुट स्टोर करने के लिए O (N) स्पेस की आवश्यकता होती है।