Дархостҳо дар бораи XOR, тақсимкунандаи тоқтарини диапазон


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад 24 * 7 Озмоишгоҳҳои инноватсионӣ Citadel Directi Expedia Google Ҳақиқатан Snapdeal
тартиботи ҳарбӣ Бит Bitwise-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 [right] -ро баргардонед.
  4. Боз як XOR-и divArray [рост] ва divArray [чап-1] -ро бармегардонад.

Шарҳ

Мо массиви бутун ва якчанд саволҳоро барои ҳалли онҳо додем. Пас аз мо хоҳиш карда мешавад, ки XOR тақсимкунандаи бузургтаринро пайдо кунем. Дархостҳо аз ду адад иборатанд. Ҳамин тавр, ин маънои онро дорад, ки мо дар доираи ин ду адад диапазон дорем. Барои ин, пеш аз ҳама, мо ҳангоми тақсим кардани массив ҳамаи тақсимкунандагони ҳар як ададро пайдо мекунем. Пас, мо рақамро аз массиви додашуда, дар як вақт гирифтанӣ ҳастем. Мо давраеро барои унсури махсусан додашуда оғоз мекунем. Дар ҳалқа, мо унсури ҷориро ба 2 тақсим карда, онро дар худи унсур нав хоҳем кард. Ин кор то он даме идома хоҳад ёфт, ки унсури ҷорӣ тоқ ҳисоб карда шавад. Вақти тоқ шудани рақам, мо берун аз ҳалқа мешиканем.

Барои ҳар як гардиши ҳар як унсури массив, натиҷаро ба тела диҳед divArray массиви, ки дар он тоқ мешавад. Чунин аст, ки дар массив унсури баробар хоҳад буд, чунон ки дар массиви додашуда. Аммо ҳамаи тақсимкунандагон дар divArray ҳастанд. Пас аз ба итмом расонидани массив, массиви дар он гузарандаро гузаред, ки дар он ҳамаи тақсимкунандагон нигоҳ дошта мешаванд. Ҳамин тавр, массиви divArray, ки ҳамаи арзишҳоро нигоҳ медорад, тақсимкунандагон аст. Сипас, мо амалиёти XOR-ро аз рӯи қиматҳои divArray иҷро карданӣ ҳастем. Мо divArray ва XOR унсури ҷорӣ ва унсури қаблии массивро мегузарем. Ва ин бояд то амалиёте, ки дар ҳар як ҷуфт анҷом дода мешавад, ҳамчун арзиши ҷорӣ ва қаблӣ анҷом дода шавад.

Ҳамин тавр, вақте ки ба мо дархост ҳамчун диапазон, чап ва рост дода мешавад. Пас мо мехоҳем тафтиш кунем, ки чап ба сифр баробар аст. Пас divArray [right] -ро баргардонед, вагарна мо XOR divArray [right] ва divArray [left-1] -ро бармегардонем.

рамз

Коди 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

Рамзи Java барои ҷавоб додан ба дархостҳо оид ба 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 log n) ки дар "N" шумораи унсурҳои массив аст. Ва аст, ки шумораи дар журнали массив мавҷудбуда пойгоҳи 2 дошта бошад. Омили log n ба сабаби тақсимоти адад то ба даст овардани тақсимоти тоқ аст.

Мураккабии фазо

О (Н) ки дар "N" шумораи унсурҳои массив аст. Мо массивро барои нигоҳ доштани арзишҳои xor истифода бурдем, ки ҷойро ишғол мекунанд.