Հարցումներ տիրույթի ամենամեծ տարօրինակ բաժանարարի XOR- ի վերաբերյալ  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են 24 * 7 նորարարության լաբորատորիաներ Միջնաբերդ Դիրեկտի Expedia Google Իսկապես Snapdeal
Դասավորություն Բիթեր Bitwise-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- ի XOR [աջ] և divArray [ձախ -1]:

բացատրություն

Մենք տվել ենք ամբողջ թվերի զանգված և որոշ հարցումներ `լուծելու: Հետո մեզ խնդրում են պարզել ամենամեծ տարօրինակ բաժանարարի XOR- ը: Հարցումները պարունակում են երկու ամբողջ թիվ: Այսպիսով, դա նշանակում է, որ մենք ունենք մի տիրույթ այդ երկու ամբողջ թվերի սահմաններում: Դրա համար, նախ և առաջ, մենք պատրաստվում ենք գտնել յուրաքանչյուր թվի բոլոր բաժանարարներին `միաժամանակ անցնելով զանգվածը: Դրանից հետո մենք միանգամից վերցնելու ենք տվյալ զանգվածից համարը: Մենք կսկսենք օղակ ՝ մասնավորապես տրված տարրի համար: Օղակում մենք շարունակելու ենք բաժանել ընթացիկ տարրը 2-ի և թարմացնել այն հենց իր մեջ: Այս բանը կշարունակվի այնքան ժամանակ, քանի դեռ չի պարզվել, որ ընթացիկ տարրը տարօրինակ է: Երբ համարը տարօրինակ կդառնա, մենք կոտրում ենք օղակից դուրս:

Տես նաեւ,
Հատուկ տարբերությամբ զույգերի առավելագույն գումար

Rayանգվածի յուրաքանչյուր տարրի յուրաքանչյուր անցման համար արդյունքը մղեք ներս divArray զանգված, որտեղ այն տարօրինակ է դառնում: Այնպիսին, որ զանգվածում կլինի հավասար տարր, ինչպես տվյալ զանգվածում: Բայց բոլոր բաժանարարները բաժանարար զանգվածում կան: Rayանգվածի ավարտից հետո անցեք այն զանգվածը, որում պահվում են բոլոր բաժանարարները: Այսպիսով, divArray զանգվածը, որը պահում է բոլոր արժեքները, բաժանարարներն են: Դրանից հետո մենք պատրաստվում ենք կատարել XOR գործողությունը divArray արժեքների վրա: Մենք պատրաստվում ենք հատել divArray- ը, և XOR- ը `ընթացիկ տարրը և զանգվածի նախորդ տարրը: Եվ այս բանը պետք է արվի մինչև յուրաքանչյուր զույգի վրա կատարված գործողությունը ՝ որպես ընթացիկ և նախորդ արժեք:

Այսպիսով, երբ մեզ հարցում են տալիս որպես միջակայք ՝ ձախ և աջ: Ապա մենք պատրաստվում ենք ստուգել, ​​արդյոք ձախը հավասար է զրոյի: Դրանից հետո վերադարձեք divArray- ը [աջ], այլապես մենք պատրաստվում ենք վերադարձնել divArray- ի XOR [աջ] և 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

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (N log n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Եվ զանգվածի մատյանում առկա թիվն ունի հիմք 2. Log n գործոնը համարի բաժանման պատճառով է, քանի դեռ մենք ստանում ենք տարօրինակ բաժանարար:

Տես նաեւ,
Նվազագույն շարժումներ հավասար զանգվածի տարրերի Leetcode լուծում

Տիեզերական բարդություն

ՎՐԱ) որտեղ «Ն» զանգվածում տարրերի քանակն է: Մենք օգտագործել ենք զանգված ՝ տարածքը խլող xor արժեքները պահելու համար: