દ્વિસંગી શબ્દમાળાઓને વૈકલ્પિક એક્સ અને વાય ઘટનાઓ તરીકે ફરીથી ગોઠવો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ભેગા સિસ્કો સિટ્રીક્સ પર્યટન IBM માહિતી એજ Pinterest Roblox ટેસ્લા
શબ્દમાળા

સમસ્યા નિવેદન

ધારો કે તમને દ્વિસંગી આપવામાં આવે છે શબ્દમાળા, અને બે નંબરો x અને y. શબ્દમાળામાં ફક્ત 0 સે અને 1 સે હોય છે. સમસ્યા "દ્વિસંગી શબ્દમાળાને વૈકલ્પિક એક્સ અને વાય ઘટનાઓ તરીકે ફરીથી ગોઠવો" શબ્દમાળાને ફરીથી ગોઠવવા માટે પૂછે છે કે 0 વખત આવે છે x વખત આવે છે ⇒ 1 આવે છે વાય ટાઇમ આવે છે ⇒ ફરીથી 0 વખત આવે છે x વખત આવે છે ⇒ 1 આવે છે અને તેથી ક્યાં 0 અથવા 1s સુધી સમાપ્ત થાય છે. પછી શબ્દમાળાના બાકીના ભાગને જોડવું અને તેને છાપો.

ઉદાહરણ

str = “01101”,

x = 1

y = 1
01011

સમજૂતી

પ્રથમ 0 મુદ્રિત x વખત, પછી 1 મુદ્રિત વાય ટાઇમ્સ, પછી 0 x વખત પછી ફરીથી 1 વાય વખત, પરંતુ હવે 0 બાકી છે તેથી આપણે શબ્દમાળાના બાકીના ભાગને 1 જેવું છે.

દ્વિસંગી શબ્દમાળાઓને વૈકલ્પિક એક્સ અને વાય ઘટનાઓ તરીકે ફરીથી ગોઠવો

 

દ્વિસંગી શબ્દમાળાઓને વૈકલ્પિક એક્સ અને વાય ઘટનાઓ તરીકે ફરીથી ગોઠવવા માટે અલ્ગોરિધમનો

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.

સમજૂતી

એક દ્વિસંગી શબ્દમાળા આપણે આપેલ ઇનપુટ તરીકે. તે દ્વિસંગી શબ્દમાળામાં ફક્ત નામ સૂચવે છે તેમ 0 અને 1 સે હોય છે. આપણને x અને y એમ બે વેલ્યુ પણ આપવામાં આવે છે. જેમ કે આપણે 0s ને આઉટપુટ શબ્દમાળામાં x વખત અને 1s ને આઉટપુટ શબ્દમાળા "y" માં સતત પુનરાવર્તિત કરવું પડશે. અને જો ત્યાં કોઈ શબ્દમાળા બાકી છે તો બાકીના શબ્દમાળાને આ આઉટપુટ શબ્દમાળા સાથે જોડો. આ માટે, અમે બંને શૂન્ય અને રાશિઓ માટે સંખ્યા અને ટ્રેક રાખવા માટે, શૂન્યકાઉન્ટ અને મુદ્દાઓ બંને માટે સરળ કાઉન્ટર સિવાય કંઈ નહીં વાપરીશું.

અમે દરેક અક્ષરને પસાર કરીશું. દરેક અક્ષર શબ્દમાળાના સ્વરૂપમાં 0 અથવા 1 હશે. અને આપણે આપેલ શબ્દમાળામાં કેટલા શૂન્ય છે અને કેટલા હાજર છે તેની ગણતરી કરીશું. શૂન્યની સંખ્યા શૂન્યકાઉન્ટમાં સંગ્રહિત કરવામાં આવશે અને જેની સંખ્યા, જેન્સકાઉન્ટમાં સંગ્રહિત કરવામાં આવશે. આ બંને ચલો આપણે ઓપરેશન કર્યા પછી પણ ઝીરો અને રાશિઓની ગણતરી રાખીશું.

શબ્દમાળામાં શૂન્ય અને રાશિઓની કુલ સંખ્યાની ગણતરી મેળવ્યા પછી. આપણે શરત સાથે લૂપ શરૂ કરીશું કે લૂપ શૂન્યકાઉન્ટ અથવા વન્સનકાઉન્ટ 0 ના થાય ત્યાં સુધી ચાલશે. તે લૂપમાં, આપણે શૂન્યકાઉન્ટ અને મુદ્દાસરની ગણતરી માટે વ્યક્તિગત રૂપે શોધીશું, એક શરત સાથે કે લૂપ x સુધી ચાલશે. લૂપમાં વેલ્યુ પહોંચી ગઈ છે. આ સમય દરમિયાન આપણે '0' છાપવા જઈશું અને શૂન્યકાઉન્ટની કિંમત ઘટાડીશું અને તેને x વખત છાપીશું. અને તે પછી બીજી લૂપ એક્ઝીક્યુટ થશે, જે '1' વાય ટાઇમ પ્રિન્ટ કરશે. પછી વ onesન્સક .ન્ટનું મૂલ્ય ઘટતા જતા રહો. આ બાકીના શબ્દમાળાને અસર થશે નહીં અને અમને ઇચ્છિત આઉટપુટ મળશે.

કોડ

દ્વિસંગી શબ્દમાળાને વૈકલ્પિક એક્સ અને વાય ઘટનાઓ તરીકે ફરીથી ગોઠવવા માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” શબ્દમાળા ની લંબાઈ છે. અહીં આપણે શબ્દમાળાની લંબાઈ જેટલી લૂપ ચલાવી. કારણ કે અમને કોઈ ખાસ રીતે સ્ટ્રિંગને ફરીથી ગોઠવવાની જરૂર હતી. અમારે તે બધાં પાત્રો છાપવાનાં હતાં જેણે તેને રેખીય સમયની જટિલતામાં ચલાવ્યું.

અવકાશ જટિલતા

ઓ (1), કારણ કે આપણે નવી સ્ટ્રિંગ સ્ટોર કરી રહ્યા નથી. આપણે ફક્ત નવા શબ્દમાળાના ઘટકો છાપીએ છીએ. તેથી આ usપરેશન માટે અમને કોઈ જગ્યા ખર્ચ થશે નહીં. અને તેથી અલ્ગોરિધમ માટે પોતે જ જગ્યાની જટિલતા સતત છે. જ્યારે સંપૂર્ણ પ્રોગ્રામને ઇનપુટ સ્ટોર કરવા માટે O (N) જગ્યાની જરૂર હોય છે.