ശ്രേണിയുടെ ഏറ്റവും വലിയ വിചിത്രമായ ഹരണത്തിന്റെ XOR- ലെ അന്വേഷണങ്ങൾ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു 24 * 7 ഇന്നൊവേഷൻ ലാബുകൾ കോട്ട ഡയറക്റ്റി ബൈ ഗൂഗിൾ തീർച്ചയായും സ്നാപ്ഡേൽ
അറേ ബിറ്റുകൾ ബിറ്റ്വൈസ്- XOR അന്വേഷണ പ്രശ്നം

പ്രശ്നം പ്രസ്താവന

“ശ്രേണിയുടെ ഏറ്റവും വിചിത്രമായ വിഭജനത്തിന്റെ XOR- ലെ അന്വേഷണങ്ങൾ” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി of പൂർണ്ണസംഖ്യ q എന്ന ചോദ്യവും ഓരോ ചോദ്യത്തിലും ഒരു ശ്രേണി അടങ്ങിയിരിക്കുന്നു. ഓരോ ചോദ്യത്തിനും നൽകിയിരിക്കുന്ന പരിധിക്കുള്ളിൽ ഏറ്റവും വലിയ വിചിത്രമായ ഹരണത്തിന്റെ XOR കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

arr[] = {2, 6, 4}
Query :(1, 2), (0, 1)
2 2

വിശദീകരണം

ഏറ്റവും വിചിത്രമായ വിഭജനം: (1,3,1)

3,1 ന്റെ XOR 2 ആണ്.

1,3 ന്റെ XOR 2 ആണ്.

ശ്രേണിയുടെ ഏറ്റവും വലിയ വിചിത്രമായ ഹരണത്തിന്റെ XOR- ലെ അന്വേഷണങ്ങൾ

 

അൽഗോരിതം

  1. തന്നിരിക്കുന്ന അറേയിലൂടെ സഞ്ചരിക്കുക.
    1. ഒരു അറേയുടെ നിലവിലെ ഘടകം വിചിത്രമാണോയെന്ന് പരിശോധിക്കുന്നത് തുടരുക, നിലവിലെ എലമെന്റിനെ ഏറ്റവും കുറഞ്ഞ ഹരിക്കൽ നമ്പർ ഉപയോഗിച്ച് അപ്‌ഡേറ്റുചെയ്യുക.
    2. സജ്ജമാക്കുക divArray നൽകിയ അറേയുടെ അപ്‌ഡേറ്റ് ഘടകത്തിലേക്കുള്ള ഘടകം.
  2. അറേ വീണ്ടും സഞ്ചരിച്ച്, ഓരോ ഘടകങ്ങളും അപ്‌ഡേറ്റുചെയ്യുക divArray നിലവിലെ മൂലകത്തിന്റെ XOR- ലും divArray അറേയുടെ മുമ്പത്തെ ഘടകത്തിലും അറേ ചെയ്യുക.
  3. ഇടത് ഘടകം 0 ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, തുടർന്ന് divArray [വലത്] നൽകുക.
  4. അല്ലാത്തപക്ഷം divArray [വലത്], divArray [ഇടത് -1] എന്നിവയുടെ XOR തിരികെ നൽകുക.

വിശദീകരണം

പരിഹരിക്കാനായി ഞങ്ങൾ ഒരു കൂട്ടം സംഖ്യകളും ചില ചോദ്യങ്ങളും നൽകി. ഏറ്റവും വലിയ വിചിത്രമായ ഹരണത്തിന്റെ XOR കണ്ടെത്താൻ ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. ചോദ്യങ്ങളിൽ രണ്ട് പൂർണ്ണസംഖ്യകൾ അടങ്ങിയിരിക്കുന്നു. അതിനാൽ, ഈ രണ്ട് സംഖ്യകൾക്കുള്ളിൽ നമുക്ക് ഒരു ശ്രേണി ഉണ്ടെന്നാണ് ഇതിനർത്ഥം. ഇതിനായി, ഒന്നാമതായി, അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ ഓരോ സംഖ്യയുടെയും എല്ലാ ഹരണങ്ങളും ഞങ്ങൾ കണ്ടെത്താൻ പോകുന്നു. ഒരു നിശ്ചിത അറേയിൽ നിന്ന് ഞങ്ങൾ ഒരു സമയം നമ്പർ എടുക്കാൻ പോകുന്നു. ഒരു, പ്രത്യേകിച്ച് നൽകിയിരിക്കുന്ന ഘടകത്തിനായി ഞങ്ങൾ ഒരു ലൂപ്പ് ആരംഭിക്കും. ലൂപ്പിൽ, നിലവിലെ ഘടകത്തെ 2 കൊണ്ട് ഹരിച്ചാൽ അത് എലമെന്റിൽ തന്നെ അപ്ഡേറ്റ് ചെയ്യും. നിലവിലെ ഘടകം വിചിത്രമാണെന്ന് കണ്ടെത്തുന്നതുവരെ ഈ കാര്യം തുടരും. നമ്പർ വിചിത്രമാകുന്ന സമയം, ഞങ്ങൾ ലൂപ്പിന് പുറത്ത് തകരുന്നു.

ഒരു അറേയിലെ ഓരോ ഘടകത്തിന്റെയും ഓരോ സഞ്ചാരത്തിനും, ഫലം അകത്തേക്ക് നീക്കുക divArray ശ്രേണി, അത് വിചിത്രമായി മാറുന്നു. തന്നിരിക്കുന്ന അറേയിലുള്ളത് പോലെ ഒരു അറേയിൽ തുല്യ ഘടകമുണ്ടാകും. എന്നാൽ എല്ലാ ഡിവിസറുകളും ഡിവിറേയിൽ ഉണ്ട്. അറേ പൂർത്തിയാക്കിയ ശേഷം, എല്ലാ ഹരണങ്ങളും സംഭരിച്ചിരിക്കുന്ന അറേയിലൂടെ സഞ്ചരിക്കുക. അങ്ങനെ, എല്ലാ മൂല്യങ്ങളും സംഭരിക്കുന്ന divArray അറേയാണ് ഹരണങ്ങൾ. തുടർന്ന് ഞങ്ങൾ divArray മൂല്യങ്ങളിൽ XOR പ്രവർത്തനം നടത്താൻ പോകുന്നു. ഞങ്ങൾ divArray, XOR എന്നിവ നിലവിലെ ഘടകവും അറേയുടെ മുമ്പത്തെ ഘടകവും സഞ്ചരിക്കാൻ പോകുന്നു. നിലവിലുള്ളതും മുമ്പത്തെതുമായ മൂല്യമായി ഓരോ ജോഡിയിലും ഓപ്പറേഷൻ നടത്തുന്നതുവരെ ഈ കാര്യം ചെയ്യണം.

അതിനാൽ, ഒരു ശ്രേണി, ഇടത്, വലത് എന്നിങ്ങനെ ഞങ്ങൾക്ക് ഒരു ചോദ്യം നൽകുമ്പോൾ. ഇടത് പൂജ്യത്തിന് തുല്യമാണോ എന്ന് പരിശോധിക്കാൻ പോകുന്നു. തുടർന്ന് divArray [വലത്തേക്ക്] മടങ്ങുക, അല്ലാത്തപക്ഷം ഞങ്ങൾ divArray [വലത്], divArray [ഇടത് -1] എന്നിവയുടെ XOR തിരികെ നൽകാൻ പോകുന്നു.

കോഡ്

ശ്രേണിയുടെ ഏറ്റവും വലിയ വിചിത്രമായ ഹരണത്തിന്റെ XOR ലെ ചോദ്യങ്ങൾക്ക് ഉത്തരം നൽകാനുള്ള സി ++ കോഡ്

#include<iostream>

using namespace std;

void getDivisorArray(int arr[], int divArray[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while (arr[i] % 2 != 1)
            arr[i] /= 2;

        divArray[i] = arr[i];
    }
    for (int i = 1; i < n; i++)
        divArray[i] = divArray[i - 1] ^ divArray[i];
}

int solveQuery(int divArray[], int left, int right)
{
    if (left == 0)
        return divArray[right];
    else
        return divArray[right] ^ divArray[left - 1];
}

int main()
{
    int arr[] = {2, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int divArray[n];
    getDivisorArray(arr, divArray, n);

    cout << solveQuery(divArray, 1, 2) << endl;
    cout << solveQuery(divArray, 0, 1) << endl;

    return 0;
}
2
2

ശ്രേണിയിലെ ഏറ്റവും വലിയ വിചിത്രമായ ഹരണത്തിന്റെ XOR- ലെ ചോദ്യങ്ങൾക്ക് ഉത്തരം നൽകാനുള്ള ജാവ കോഡ്

class QueriesXOR
{
    public static void getDivisorArray(int arr[], int divArray[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            while (arr[i] % 2 != 1)
                arr[i] /= 2;

            divArray[i] = arr[i];
        }
        for (int i = 1; i < n; i++)
            divArray[i] = divArray[i - 1] ^ divArray[i];
    }
    
    static int solveQuery(int divArray[], int l, int r)
    {
        if (l == 0)
            return divArray[r];
        else
            return divArray[r] ^ divArray[l - 1];
    }
    
    public static void main (String[] args)
    {
        int arr[] = {2, 6, 4};
        int n = arr.length;

        int divArray[] = new int[n];
        getDivisorArray(arr, divArray, n);

        System.out.println(solveQuery(divArray, 1, 2)) ;
        System.out.println (solveQuery(divArray, 0, 1));
    }
}
2
2

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N ലോഗ് n) എവിടെ "N" അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഒപ്പം അറേ ലോഗിൽ നിലവിലുള്ള സംഖ്യയ്ക്ക് ബേസ് 2 ഉണ്ട്. നമുക്ക് ഒരു വിചിത്രമായ ഹരിക്കൽ ലഭിക്കുന്നതുവരെ സംഖ്യ വിഭജനം മൂലമാണ് ലോഗ് n ഘടകം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) എവിടെ "N" അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. സ്‌പെയ്‌സ് എടുക്കുന്ന xor മൂല്യങ്ങൾ സംഭരിക്കാൻ ഞങ്ങൾ ഒരു അറേ ഉപയോഗിച്ചു.