Упити о КСОР-у највећег непарног делиоца опсега  


Ниво тешкоће Средњи
Често питани у 24 * 7 лабораторија за иновације Цитадела Дирецти Екпедиа гоогле Заиста Снапдеал
Ред Битс Бит-КСОР Куери Проблем

Изјава о проблему  

Проблем „Упити о КСОР-у највећег непарног делиоца опсега“ наводи да сте добили поредак of цео број и упит к, сваки упит се састоји од опсега. Изјава о проблему тражи да се за сваки упит пронађе КСОР највећег непарног делитеља у датом опсегу.

Пример  

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

Објашњење

Највећи непарни делилац: (1,3,1)

КСОР од 3,1 је 2.

КСОР од 1,3 је 2.

Упити о КСОР-у највећег непарног делиоца опсегаПин

 

Алгоритам  

  1. Пређите преко датог низа.
    1. Наставите да проверавате тренутни елемент низа ако је непаран и ажурирајте тренутни елемент за најмањи број делитеља.
    2. Подесите дивАрраи елемент на елемент ажурирања датог низа.
  2. Поново пређите низ и ажурирајте сваки елемент дивАрраи низа у КСОР тренутног елемента и претходног елемента низа дивАрраи.
  3. Проверите да ли је леви елемент једнак 0, а затим вратите дивАрраи [десно].
  4. Иначе враћају КСОР дивАрраи [десно] и дивАрраи [лево-1].

Објашњење

Дали смо низ целих бројева и неколико упита за решавање. Тада се од нас тражи да сазнамо КСОР највећег непарног делитеља. Упити садрже две целобројне вредности. Дакле, то значи да имамо распон унутар те две целобројне вредности. За ово ћемо, пре свега, пронаћи све делиоце сваког броја, док прелазимо низ. Тада ћемо покупити број из датог низа, истовремено. Започећемо петљу за, посебно дати елемент. У петљи ћемо наставити да делимо тренутни елемент са 2 и ажурирати га у самом елементу. Ова ствар ће се наставити док се не утврди да ли је тренутни елемент чудан. Када број постане непаран, прекинемо се изван петље.

Види такође
Максимални збир парова са одређеном разликом

За сваки обилазак сваког елемента низа, гурните резултат у дивАрраи низ, где постаје чудно. Такав да ће у низу бити једнак елемент као у датом низу. Али сви делитељи су тамо у дивАрраи-у. Након завршетка низа, пређите низ у којем су смештени сви делитељи. Дакле, дивАрраи низ који чува све вредности су делитељи. Тада ћемо извршити КСОР операцију над вредностима дивАрраи. Прећи ћемо дивАрраи и КСОР тренутни елемент и претходни елемент низа. И то би требало радити до операција изведених на сваком пару као тренутна и претходна вредност.

Дакле, када нам се даје упит као опсег, лево и десно. Тада ћемо проверити да ли је лево једнако нули. Затим вратите дивАрраи [десно], иначе ћемо вратити КСОР дивАрраи [десно] и дивАрраи [лево-1].

код  

Ц ++ код за одговарање на упите на КСОР највећег непарног делитеља опсега

#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

Јава код за одговарање на упите на КСОР највећег непарног делиоца опсега

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

Анализа сложености  

Сложеност времена

О (Н лог н) где "Н" је број елемената у низу. И је број присутан у низу лог има базу 2. Фактор лог н је због поделе броја док не добијемо непаран делитељ.

Види такође
Минимално премештање једнаког низа елемената Леетцоде решење

Сложеност простора

НА) где "Н" је број елемената у низу. Користили смо низ за чување кор вредности које заузимају простор.