XOR боюнча суроолор диапазондун эң чоң так бөлүштүргүчүнө байланыштуу


Кыйынчылык деңгээли орто
Көп суралган 24 * 7 Innovation Labs Citadel Directi Expedia Гугл Чындыгында Snapdeal
согуштук тизме Bits Bitwise-XOR Query Problem

Маселени билдирүү

"Диапазондун эң чоң так бөлүштүргүчүнүн XOR сурамдары" көйгөйүндө сизге an берилген согуштук тизме 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 боюнча суроолор диапазондун эң чоң так бөлүштүргүчүнө байланыштуу

 

Algorithm

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

түшүндүрүү

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

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

Ошентип, бизге сурам берилгенде, солго жана оңго. Анда биз сол нөлгө барабар экендигин текшеребиз. Андан кийин divArray [оңго] кайтарыңыз, болбосо биз XOR divArray [оңго] жана divArray [солго-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 коэффициенти сандын такка бөлүнгүчүн алганга чейин бөлүнгөндүктөн болот.

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Биз орун алган xor баалуулуктарын сактоо үчүн массивди колдондук.