எம் வரம்பிற்குள் பைனரி வரிசை செயல்பாடுகளை மாற்று


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் Coursera கூடுதலாக கோல்ட்மேன் சாக்ஸ் கூகிள் கிரே ஆரஞ்சு SnapChat
அணி வினவல் சிக்கல்

உங்களுக்கு ஒரு பைனரி வரிசை வழங்கப்படுகிறது, இது ஆரம்பத்தில் 0 மற்றும் Q வினவல்களைக் கொண்டுள்ளது. சிக்கல் அறிக்கை மதிப்புகளை நிலைமாற்றக் கேட்கிறது (0 களை 1 வி மற்றும் 1 வி 0 களாக மாற்றுகிறது). Q வினவல்கள் நிகழ்த்தப்பட்ட பிறகு, விளைவாக வரிசையை அச்சிடுக.

உதாரணமாக

arr[] = {0, 0, 0, 0, 0}

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

விளக்கம்

1 வது நிலைமாற்றம்   0,1,1,1,0

2 வது நிலைமாற்றம் 1,0,1,1,0

3 வது மாறுதல் 1,0,0,0,1

எம் வரம்பிற்குள் பைனரி வரிசை செயல்பாடுகளை மாற்று

அல்காரிதம்

  1. N + 2 அளவிலான பூலியன் வரிசையை உருவாக்கவும்.
  2. ஒவ்வொரு குறியீட்டிற்கும் பூலியன் வரிசையை தவறானது எனத் தொடங்கவும்.
  3. இப்போது ஒவ்வொரு வினவலுக்கும் இடது மற்றும் வலது + 1 குறியீட்டில் உள்ள உறுப்பை புரட்டவும்.
  4. இப்போது வரிசையை முன்னொட்டு xor வரிசையாக நிரப்பவும். குறியீட்டு 1 முதல் i வரையிலான அனைத்து உறுப்புகளின் xor ஐ குறியீட்டு i இல் சேமிக்கவும்.
  5. வரிசையை அச்சிடுக

எம் வரம்பு மாற்று செயல்பாடுகளுக்குப் பிறகு பைனரி வரிசைக்கான விளக்கம்

ஒரு பைனரி கொடுக்கப்பட்டது வரிசை, இது 0 வி மற்றும் 1 வி மற்றும் பெயர் குறிப்பிடுவதைக் கொண்டுள்ளது. ஆனால் ஆரம்பத்தில், இது 0 கள் என மதிப்புகளை மட்டுமே கொண்டுள்ளது. வினவல்களின் Q எண் கொடுக்கப்பட்டுள்ளது. ஒவ்வொரு வினவலும் இரண்டு மதிப்புகளைக் கொண்டுள்ளது, மதிப்புகள் ஒரு வரம்பின் தொடக்கப் புள்ளி மற்றும் ஒரு வரம்பின் இறுதிப் புள்ளி, இந்த வரம்புகளுக்குள், நாம் மதிப்புகளை மாற்ற வேண்டும், அங்கு மாறுவது என்றால் 0 களை 1 வி மற்றும் 1 வி 0 க Q எண்ணாக மாற்ற வேண்டும் ( வினவல் எண்) முறை. இதற்காக, நாம் ஒரு உருவாக்கப் போகிறோம் பூலியன் வரிசை, அளவு இரண்டு + வரிசையின் நீளம் n + 2. Q மதிப்புகளை பல முறை மாற்றுவதற்குப் போகிறோம், நம்மிடம் அதிகமான கேள்விகள் இருந்தால், அதை நம் சுயமாக அழைக்க வேண்டியதில்லை, அதற்கு பதிலாக, நாம் ஒரு வட்டத்தை உருவாக்கி வெவ்வேறு வினவல் எண் மற்றும் உள்ளீடுகளுடன் அழைப்போம்.

மாறுதலில், ஒரே வரிசையில் ஒரு வரம்பாக கொடுக்கப்பட்ட சரியான இடங்களில் மதிப்புகளை மாற்றவும், அனைத்து பூஜ்ஜியங்களையும் ஒன்றாகவும், XOR செயல்பாட்டைச் செய்வதன் மூலம் அதை பூஜ்ஜியமாகவும் மாற்றவும். அதே எண்கள் அல்லது மதிப்புகள் கண்டுபிடிக்கப்பட்டால் XOR செயல்பாடும் நமக்கு அவ்வாறே செய்கிறது, இது 0 ஐ கொடுக்கும், இதன் விளைவாக வேறுபட்ட மதிப்புகளைக் கண்டறிந்தால் அது பொய் என்று பொருள். இது 1 ஐ கொடுக்கும், இதன் விளைவாக, உண்மை என்று பொருள். எனவே மதிப்புகளைத் திருப்புவதற்கு மாறுதல் செயல்பாட்டிலும் இதைச் செய்வோம்.

வரிசையில் பயணிக்கவும், வரிசையில் செயல்பாட்டைச் செய்யவும். தற்போதைய மற்றும் வரிசையின் முந்தைய மதிப்பில் XOR செயல்பாட்டைச் செய்யவும். அதே பிட்டைக் கண்டறிந்தால் நாம் செய்த காரியம் 0 இல்லையெனில் 1 ஐக் கொடுக்கும். இந்த செயல்பாடு ஒரு வரம்பிற்குள் மாறும் அனைத்து மதிப்புகளையும் மாற்றுவதற்கான கடைசி முறையாகும். இறுதியாக, வரிசையை அச்சிடுக.

குறியீடு

எம் வரம்பு மாற்று செயல்பாடுகளுக்குப் பிறகு பைனரி வரிசைக்கு சி ++ இல் செயல்படுத்தல்

#include<iostream>

using namespace std;

void Toggle(bool arr[], int start, int end)
{
    arr[start] ^= 1;
    arr[end+1] ^= 1;
}

void getToggling(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}

void printOutput(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        cout << arr[k] <<" ";
}

int main()
{
    int n = 5, m = 3;
    bool arr[n+2] = {0};

    Toggle(arr, 1, 5);
    Toggle(arr, 2, 5);
    Toggle(arr, 3, 5);

    getToggling(arr, n);

    printOutput(arr, n);
    return 0;
}
1 0 1 1 1

எம் வரம்பு மாற்று செயல்பாடுகளுக்குப் பிறகு பைனரி வரிசைக்கு ஜாவாவில் செயல்படுத்தல்

class ToggleArray
{
    static void Toggle(boolean arr[], int start, int end)
    {
        arr[start] ^= true;
        arr[end + 1] ^= true;
    }

    static void getToggling(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            arr[k] ^= arr[k - 1];
        }
    }

    static void printOutput(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            if(arr[k] == true)
                System.out.print("1" + " ");
            else
                System.out.print("0" + " ");
        }
    }

    public static void main(String args[])
    {
        int n = 5, m = 3;
        boolean arr[] = new boolean[n + 2];

        Toggle(arr, 1, 5);
        Toggle(arr, 2, 5);
        Toggle(arr, 3, 5);

        getToggling(arr, n);

        printOutput(arr, n);
    }
}
1 0 1 1 1

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (n + q) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை மற்றும் “q”என்பது வினவல்களின் எண்ணிக்கை. அனைத்து வினவல்களும் O (1) நேரத்தில் செய்யப்படுகின்றன, பின்னர் புதுப்பிப்புக்கு O (N) நேரம் தேவைப்படுகிறது.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.