বিকল্প x এবং y উপস্থিতি হিসাবে একটি বাইনারি স্ট্রিং পুনরায় সাজান


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি সিসকো Citrix আরোহণ আইবিএম তথ্য প্রান্ত পিন্টারেস্ট Roblox টেসলা
স্ট্রিং

সমস্যা বিবৃতি

ধরুন আপনাকে বাইনারি দেওয়া হয়েছে স্ট্রিং, এবং দুটি সংখ্যা x এবং y। স্ট্রিংটি কেবল 0 সে এবং 1 এস নিয়ে থাকে। সমস্যাটি "বাইনারি স্ট্রিংটিকে বিকল্প x এবং y উপস্থিতি হিসাবে পুনরায় সাজান" স্ট্রিংটিকে পুনরায় সাজিয়ে তুলতে বলে যে 0 টি আসে x বার ⇒ 1 আসে y বার ⇒ আবার 0 আসে x বার ⇒ 1 আসে y বার এবং তাই 0 বা 1s পর্যন্ত শেষ তারপরে স্ট্রিংয়ের অবশিষ্ট অংশটি কনটেনেট করে মুদ্রণ করুন।

উদাহরণ

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.

ব্যাখ্যা

একটি বাইনারি স্ট্রিং একটি ইনপুট হিসাবে আমরা দিয়েছেন। এই বাইনারি স্ট্রিংটিতে কেবলমাত্র নাম অনুসারে 0 সে এবং 1 এস থাকে। আমাদের এক্স এবং y দুটি মান দেওয়া হয়। এমন যে আমাদের 0s গুলি আউটপুট স্ট্রিংয়ে x বার এবং 1s আউটপুট স্ট্রিং "y" বারে একটানা বারবার করতে হবে। এবং যদি কোনও স্ট্রিং বাম থাকে তবে এই আউটপুট স্ট্রিং সহ বাকী স্ট্রিংটি সংযুক্ত করুন। এর জন্য, আমরা জিরো এবং উভয়র জন্য সংখ্যা এবং ট্র্যাকগুলি রাখতে জিরো কাউন্ট এবং জিনসকাউন্ট উভয়ের জন্য একটি সাধারণ কাউন্টার ছাড়া আর কিছুই ব্যবহার করতে যাচ্ছি।

আমরা প্রতিটি অক্ষরের স্ট্রিংটি অতিক্রম করতে যাচ্ছি। প্রতিটি অক্ষর একটি স্ট্রিং আকারে 0 বা 1 হবে। এবং আমরা গণনা করব যে প্রদত্ত স্ট্রিংয়ে কয়টি শূন্য এবং কতজন উপস্থিত রয়েছে? জিরো সংখ্যা জিরো কাউন্টে সংরক্ষণ করা হবে এবং এর সংখ্যা ওয়ানকোয়েন্টে সংরক্ষণ করা হবে। এই দুটি ভেরিয়েবলগুলি আমাদের অপারেশন করার পরেও শূন্য এবং এর সংখ্যা গণনা করবে।

একটি স্ট্রিংয়ে মোট শূন্য এবং এর মোট সংখ্যা গণনা করার পরে। আমরা একটি শর্ত দিয়ে একটি লুপ শুরু করব যে লুপটি শূন্যগুণ বা টিপসাউন্ট 0 না হওয়া অবধি চলবে that সেই লুপটিতে আমরা পৃথকভাবে একটি শূন্যসমাউন্ট এবং ডেস্কউন্টের সন্ধান করব, এই শর্তে লুপটি এক্স পর্যন্ত অবধি চলবে মান একটি লুপ পৌঁছেছে। এই সময়ের মধ্যে আমরা '0' মুদ্রণ করব এবং জিরোকাউন্টের মান হ্রাস করব এবং এটি x বার মুদ্রণ করব। এবং এর পরে আর একটি লুপ কার্যকর হবে, যা '1' y বার মুদ্রণ করবে। তারপরে ওয়ানকাউন্টের মান হ্রাস করতে থাকুন। এই বাকি স্ট্রিংটি প্রভাবিত হবে না এবং আমরা পছন্দসই আউটপুট পাব।

কোড

বিকল্প x এবং 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

বিকল্প 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

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" স্ট্রিংয়ের দৈর্ঘ্য। এখানে আমরা স্ট্রিংয়ের দৈর্ঘ্যের সমান লুপটি চালাই। কারণ আমাদের একটি নির্দিষ্ট পদ্ধতিতে স্ট্রিংটিকে পুনরায় সাজানো দরকার ছিল। আমাদের সমস্ত অক্ষর মুদ্রণ করতে হয়েছিল যা এটি রৈখিক সময়ের জটিলতায় চালিত করে।

স্পেস জটিলতা ity

ও (1), কারণ আমরা নতুন স্ট্রিংটি স্টোর করছি না। আমরা কেবল নতুন স্ট্রিংয়ের উপাদানগুলি মুদ্রণ করছি। সুতরাং এই অপারেশনটি আমাদের কোনও জায়গার ব্যয় করে না। এবং সেইজন্য নিজেই অ্যালগরিদমের জন্য স্থান জটিলতা ধ্রুবক। যদিও পুরো প্রোগ্রামটির জন্য ইনপুট সংরক্ষণের জন্য O (N) স্পেস প্রয়োজন।