XOR бойынша сұраныстар диапазонның ең үлкен тақ бөлгіші


Күрделілік дәрежесі орта
Жиі кіреді 24 * 7 инновациялық зертханалар Цитадель Directi Expedia Google шынында Шапшаң
Array Биттер Разрядты-XOR Сұрақ мәселесі

Проблемалық мәлімдеме

«Диапазонның ең үлкен тақ бөлгішінің XOR бойынша сұраулар» деген есеп сізге берілгенін айтады массив of бүтін сан және q сұранысы, әр сұраныс ауқымнан тұрады. Проблемалық сұрақ әр сұраныс үшін берілген диапазондағы ең үлкен тақ бөлгіштің XOR-ын табуды сұрайды.

мысал

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

Түсіндіру

Ең үлкен тақ бөлгіш: (1,3,1)

XOR 3,1 - 2.

XOR 1,3 - 2.

XOR бойынша сұраныстар диапазонның ең үлкен тақ бөлгіші

 

Алгоритм

  1. Берілген жиым бойынша жүріңіз.
    1. Массивтің ағымдағы элементін тақ болса тексеріп отырыңыз және ағымдағы элементті ең кіші бөлгіш санымен жаңартыңыз.
    2. Орнатыңыз divArray берілген жиымның жаңарту элементіне элемент.
  2. Массивті тағы бір айналып өтіп, -ның әрбір элементін жаңартыңыз divArray жиым ағымдағы элементтің XOR және divArray массивінің алдыңғы элементіне.
  3. Сол жақ элементтің 0-ге тең екендігін тексеріп, divArray [оңға] қайтарыңыз.
  4. DivArray [оңға] және divArray [сол жаққа-1] XOR қайтарады.

Түсіндіру

Біз бүтін сандар жиынын және шешуге арналған бірнеше сұраныстар бердік. Содан кейін бізден ең үлкен тақ бөлгіштің XOR-ын анықтауды сұрайды. Сұрауларда екі бүтін сан бар. Демек, бұл бізде осы екі бүтін санның ауқымы бар деген сөз. Ол үшін, ең алдымен, біз массивті айналып өтіп, әр санның барлық бөлгіштерін табамыз. Содан кейін біз берілген жиымнан нөмірді бір уақытта жинаймыз. Біз, әсіресе берілген элемент үшін циклды бастаймыз. Циклде біз ағымдағы элементті 2-ге бөлуді жалғастырамыз және оны элементтің өзінде жаңартамыз. Бұл ағымдағы элемент тақ болып табылмайынша жалғасады. Нөмір тақ болатын уақыт, біз циклден тыс шығамыз.

Массивтің әрбір элементінің өтуі үшін нәтижені итеріңіз divArray массив, онда тақ болады. Алапта берілген массивтегідей тең элемент болатындай. Бірақ бөлгіштердің барлығы divArray-да бар. Массив аяқталғаннан кейін барлық бөлгіштер сақталатын массивтен өтіңіз. Осылайша, барлық мәндерді сақтайтын divArray жиымы бөлгіштер болып табылады. Содан кейін біз divArray мәндері бойынша XOR операциясын орындаймыз. Біз divArray және XOR массивтің ағымдық және алдыңғы элементін өтеміз. Бұл әр жұпта орындалған операцияға дейінгі және алдыңғы мән ретінде жасалуы керек.

Сонымен, бізге сұрау диапазон ретінде берілгенде, солға және оңға. Сонда біз сол жақтың нөлге тең екендігін тексереміз. Содан кейін divArray [оңға] қайтарыңыз, әйтпесе біз divArray [оңға] және divArray [сол жаққа-1] XOR қайтарамыз.

код

C ++ коды, диапазонның ең үлкен тақ бөлгішінің 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 бойынша сұраныстарға жауап беретін Java коды, диапазонның ең үлкен тақ бөлгіші

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 log n) қайда «N» - бұл массивтегі элементтер саны. Және жиым журналында келтірілген санның 2-негізі болады. Log n коэффициенті санның бөлінуіне байланысты, біз тақ бөлгішті алғанға дейін.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз бос орын алатын xor мәндерін сақтау үшін массив қолдандық.