بائنری سٹرنگ کو بطور متبادل x اور y واقعات کو دوبارہ ترتیب دیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اکٹھا کرنا سسکو Citrix کی اضافہ IBM انفارمیشن ایج Pinterest پر Roblox Tesla
سلک

مسئلہ یہ بیان

فرض کریں کہ آپ کو بائنری دیا گیا ہے سٹرنگ، اور دو نمبر x اور y۔ تار صرف 0s اور 1s پر مشتمل ہے۔ مسئلہ "بائنری سٹرنگ کو بطور متبادل x اور y واقعات کو دوبارہ ترتیب دیں" اس تار کو دوبارہ ترتیب دینے کے لئے کہتا ہے کہ 0 بار آتا ہے x اوقات ⇒ 1 آتا ہے y بار ⇒ پھر 0 آتا ہے x اوقات ⇒ 1 آتا ہے اور اسی طرح 0 یا 1s تک ختم ہوچکے ہیں۔ اس کے بعد تار کے باقی حصے پر اتفاق کریں اور اسے پرنٹ کریں۔

مثال کے طور پر

str = “01101”,

x = 1

y = 1
01011

وضاحت

پہلے 0 پرنٹ شدہ ایکس ٹائم ، پھر 1 پرنٹ ی ٹائم ، پھر 0 ایکس اوقات پھر دوبارہ 1 ی ٹائم ، لیکن اب 0 باقی ہے لہذا ہم سٹرنگ کے بقیہ حصے کو 1 کے مطابق کرتے ہیں۔

بائنری سٹرنگ کو بطور متبادل x اور y واقعات کو دوبارہ ترتیب دیں

 

بائنری سٹرنگ کو متبادل x اور y واقعات کی بحالی کے ل Al الگورتھم

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 بھی دیئے گئے ہیں۔ اس طرح کہ ہمیں 0s کو آؤٹ پٹ سٹرنگ میں x اوقات اور 1s کو آؤٹ پٹ سٹرنگ "y" میں مسلسل دہرانا پڑتا ہے۔ اور اگر کوئی سٹرنگ باقی ہے تو باقی سٹرنگ کو اس آؤٹ پٹ سٹرنگ کے ساتھ موافق بنائیں۔ اس کے ل we ، ہم زیرو اور دونوں کے ل ones نمبر اور ٹریک رکھنے کے ل keep ، زیروکونٹ اور جیونساؤنٹ دونوں کے لئے ایک آسان کاؤنٹر کے علاوہ کچھ بھی استعمال نہیں کریں گے۔

ہم ہر خط کو عبور کرنے جارہے ہیں۔ ہر خط یا تو 0 یا 1 تار کی شکل میں ہوگا۔ اور ہم گنیں گے کہ دیئے گئے تار میں کتنے زیرو ہیں اور کتنے ہیں؟ زیرو کی تعداد کو زیروکاونٹ میں ذخیرہ کیا جائے گا اور انکی تعداد کو جیونکاؤنٹ میں محفوظ کیا جائے گا۔ یہ دونوں متغیر ہمارے آپریشن انجام دینے کے بعد بھی زیرو اور ان کی گنتی کو برقرار رکھیں گے۔

کسی تار میں صفروں اور افراد کی کل تعداد گننے کے بعد۔ ہم اس شرط کے ساتھ ایک لوپ شروع کریں گے جب تک کہ لوپ چلتا رہے گا یہاں تک کہ صفرکاونٹ یا اس کاؤنٹر 0 ہوجائے گا۔ اس لوپ میں ، ہم انفرادی طور پر ایک صفرکاؤنٹ اور جیسی کاؤنٹر کے لئے جارہے ہوں گے ، اس شرط کے ساتھ کہ لوپ ایکس تک جاری رہے گا۔ قیمت لوپ تک پہنچ جاتی ہے۔ اس وقت کے دوران ہم '0' پرنٹ کریں گے اور زیروکونٹ کی قدر کو کم کریں گے اور اسے ایکس مرتبہ پرنٹ کریں گے۔ اور اس کے بعد ایک اور لوپ پر عملدرآمد کیا جائے گا ، جو '1' y اوقات پرنٹ کرے گا۔ پھر ویسنکاؤنٹ کی قدر کم کرتے رہیں۔ اس کے باقی تار متاثر نہیں ہوں گے اور ہمیں مطلوبہ آؤٹ پٹ ملے گا۔

ضابطے

بائنری سٹرنگ کو متبادل x اور y واقعات کی بحالی کیلئے C ++ کوڈ

#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

بائنری سٹرنگ کو متبادل x اور y واقعات کی بحالی کیلئے جاوا کوڈ

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

اے (ن) کہاں "این" تار کی لمبائی ہے۔ یہاں ہم نے تار کی لمبائی کے برابر لوپ چلایا۔ اس وجہ سے کہ ہمیں کسی خاص انداز میں سٹرنگ کو دوبارہ ترتیب دینے کی ضرورت تھی۔ ہمیں تمام کرداروں کو پرنٹ کرنا پڑا جس کی وجہ سے یہ وقتی پیچیدگی میں چلتا رہا۔

خلائی پیچیدگی

O (1) ، کیونکہ ہم نیا تار محفوظ نہیں کررہے ہیں۔ ہم صرف نئے تار کے عناصر پرنٹ کر رہے ہیں۔ لہذا اس آپریشن سے ہمیں کسی جگہ کی لاگت نہیں آتی۔ اور اسی وجہ سے خود الگورتھم کے لئے جگہ کی پیچیدگی مستقل ہے۔ جبکہ پورا پروگرام ان پٹ کو اسٹور کرنے کے لئے O (N) جگہ کی ضرورت ہے۔