សំណួរនៅលើ XOR នៃការបែងចែកសេសធំបំផុតនៃជួរ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ បន្ទប់ពិសោធន៍ច្នៃប្រឌិត ២៤ * ៧ Citadel Directi Expedia ក្រុមហ៊ុន google ជា​ការ​ពិត Snapdeal
អារេ ប៊ីត ប៊ីតខ័រ - ហ្ស័រ បញ្ហាសំណួរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ សំណួរនៅលើអ៊ិចអរនៃការបែងចែកសេសធំបំផុតនៃជួរ” ចែងថាអ្នកត្រូវបានផ្តល់ឱ្យ អារេ of integer និងសំណួរ q រាល់សំណួរនីមួយៗមានជួរ។ សេចក្តីថ្លែងបញ្ហាស្នើឱ្យរក XOR នៃចំនួនគត់សេសធំបំផុតនៅក្នុងជួរដែលបានផ្តល់សម្រាប់សំណួរនីមួយៗ។

ឧទាហរណ៍

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

ការពន្យល់

តួចែកធំបំផុត៖ (១.៣,១)

XOR នៃ 3,1 គឺ 2 ។

XOR នៃ 1,3 គឺ 2 ។

សំណួរនៅលើ XOR នៃការបែងចែកសេសធំបំផុតនៃជួរ

 

ក្បួនដោះស្រាយ

  1. ឆ្លងកាត់អារេដែលបានផ្តល់ឱ្យ។
    1. បន្តត្រួតពិនិត្យធាតុបច្ចុប្បន្ននៃអារេប្រសិនបើវាសេសហើយធ្វើបច្ចុប្បន្នភាពធាតុបច្ចុប្បន្នដោយលេខតួចែកតិចបំផុត។
    2. កំណត់ divArray ធាតុទៅធាតុធ្វើឱ្យទាន់សម័យនៃអារេដែលបានផ្តល់ឱ្យ។
  2. ឆ្លងកាត់អារេម្តងទៀតនិងធ្វើបច្ចុប្បន្នភាពធាតុនីមួយៗនៃ divArray អារេទៅ XOR នៃធាតុបច្ចុប្បន្ននិងធាតុមុននៃអារេអារេ។
  3. ពិនិត្យមើលថាតើធាតុខាងឆ្វេងស្មើនឹង ០ បន្ទាប់មកត្រឡប់ divArray [ស្តាំ] ។
  4. ផ្សេងទៀតប្រគល់ XOR នៃ divArray [ស្តាំ] និង divArray [ឆ្វេង -១] ។

ការពន្យល់

យើងបានផ្តល់នូវចំនួនគត់និងសំណួរមួយចំនួនដើម្បីដោះស្រាយ។ បន្ទាប់មកយើងត្រូវបានគេស្នើសុំឱ្យរក XOR នៃអ្នកបែងចែកសេសដ៏អស្ចារ្យបំផុត។ សំណួរមានចំនួនគត់ពីរ។ ដូច្នេះវាមានន័យថាយើងមានជួរនៅក្នុងចំនួនគត់ទាំងពីរ។ សម្រាប់បញ្ហានេះដំបូងយើងនឹងរកអ្នកចែកទាំងអស់នៃលេខនីមួយៗខណៈពេលឆ្លងកាត់ជួរអារេ។ បន្ទាប់មកយើងនឹងទៅយកលេខពីអារេដែលបានផ្តល់ឱ្យក្នុងពេលតែមួយ។ យើងនឹងចាប់ផ្តើមរង្វិលជុំសម្រាប់ធាតុដែលបានផ្តល់ជាពិសេស។ នៅក្នុងរង្វិលជុំយើងនឹងបន្តបែងចែកធាតុបច្ចុប្បន្នដោយ 2 ហើយធ្វើបច្ចុប្បន្នភាពវានៅក្នុងធាតុដោយខ្លួនឯង។ រឿងនេះនឹងបន្តរហូតដល់ធាតុបច្ចុប្បន្នមិនត្រូវបានរកឃើញថាជាសេស។ ពេលវេលាដែលលេខនឹងក្លាយជាសេសយើងបំបែកនៅខាងក្រៅរង្វិលជុំ។

ចំពោះការឆ្លងកាត់នៃធាតុនីមួយៗនៃអារេមួយជំរុញលទ្ធផល divArray អារេដែលជាកន្លែងដែលវាក្លាយជាសេស។ ដូចជាថាវានឹងមានធាតុស្មើគ្នានៅក្នុងអារេមួយដូចដែលមាននៅក្នុងអារេដែលបានផ្តល់ឱ្យ។ ប៉ុន្តែអ្នកបែងចែកទាំងអស់មាននៅក្នុងការបែងចែក។ បនា្ទាប់ពីការបញ្ចប់អារេរួចឆ្លងកាត់អារេដែលផ្នែកចែកទាំងអស់ត្រូវបានរក្សាទុក។ ដូច្នេះអារេ divArray ដែលកំពុងរក្សាទុកតម្លៃទាំងអស់គឺ divisors ។ បន្ទាប់មកយើងនឹងអនុវត្តប្រតិបត្តិការ XOR លើតម្លៃ divArray ។ យើងនឹងឆ្លងកាត់ divArray និង XOR ធាតុបច្ចុប្បន្ននិងធាតុមុននៃអារេ។ ហើយរឿងនេះគួរតែត្រូវបានធ្វើរហូតដល់ប្រតិបត្តិការដែលបានអនុវត្តលើគូនីមួយៗជាតម្លៃបច្ចុប្បន្ននិងមុន។

ដូច្នេះនៅពេលយើងត្រូវបានផ្តល់សំណួរជាជួរខាងឆ្វេងនិងស្តាំ។ បន្ទាប់មកយើងនឹងពិនិត្យមើលថាតើខាងឆ្វេងស្មើនឹងសូន្យ។ បន្ទាប់មកត្រឡប់ divArray [ស្តាំ] បើមិនដូច្នេះទេយើងនឹងត្រឡប់ XOR នៃ divArray [ស្តាំ] និង divArray [ខាងឆ្វេង -១] ។

លេខកូដ

លេខកូដ 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 នៃការបែងចែកសេសធំបំផុតនៃជួរ

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” គឺជាចំនួនធាតុក្នុងអារេ។ និង គឺលេខដែលមាននៅក្នុង log log មានគោល ២ ។ កត្តា n log គឺដោយសារតែការបែងចែកលេខរហូតដល់យើងទទួលបាន divisor សេស។

ភាពស្មុគស្មាញនៃលំហ

O (N) ដែលជាកន្លែងដែល “ N” គឺជាចំនួនធាតុក្នុងអារេ។ យើងបានប្រើអារេមួយដើម្បីរក្សាទុកតម្លៃ xor ដែលកំពុងយកទំហំ។