ການສອບຖາມກ່ຽວກັບ XOR ຂອງການແບ່ງປັນຄີກທີ່ຍິ່ງໃຫຍ່ທີ່ສຸດຂອງລະດັບ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຫ້ອງທົດລອງປະດິດສ້າງ 24 * 7 Citadel Directi Expedia ກູໂກ ແທ້ຈິງແລ້ວ Snapdeal
Array ບິດ Bitwise-XOR ບັນຫາການສອບຖາມ

ຖະແຫຼງການບັນຫາ

ບັນຫາ "ການສອບຖາມກ່ຽວກັບ XOR ຂອງການແບ່ງປັນຄວາມຄີກທີ່ຍິ່ງໃຫຍ່ທີ່ສຸດຂອງລະດັບ" ກ່າວວ່າທ່ານໄດ້ຖືກມອບໃຫ້ array of integer ແລະແບບສອບຖາມ 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 array ຫາ XOR ຂອງປັດຈຸບັນແລະອົງປະກອບທີ່ຜ່ານມາຂອງ divArray array.
  3. ກວດເບິ່ງວ່າອົງປະກອບດ້ານຊ້າຍເທົ່າກັບ 0, ຫຼັງຈາກນັ້ນສົ່ງ divArray [ຢູ່ເບື້ອງຂວາ].
  4. ອື່ນໃຫ້ກັບຄືນ XOR ຂອງ divArray [ຂວາ] ແລະ divArray [ຊ້າຍ-1].

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ໃຫ້ຫລາຍໆເລກຂອງເລກເຕັມແລະບາງ ຄຳ ຖາມເພື່ອແກ້ໄຂ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຖືກຮ້ອງຂໍໃຫ້ຊອກຫາ XOR ຂອງການແບ່ງປັນທີ່ໃຫຍ່ທີ່ສຸດ. ແບບສອບຖາມມີສອງເລກ. ດັ່ງນັ້ນ, ມັນ ໝາຍ ຄວາມວ່າພວກເຮົາມີຊ່ວງຢູ່ພາຍໃນສອງຕົວເລກເຫລົ່ານັ້ນ. ສຳ ລັບສິ່ງນີ້, ກ່ອນອື່ນ ໝົດ, ພວກເຮົາ ກຳ ລັງຈະຊອກຫາຕົວເລກທັງ ໝົດ ຂອງແຕ່ລະຕົວເລກ, ໃນຂະນະທີ່ ກຳ ລັງຂ້າມແຖວ. ຫຼັງຈາກນັ້ນພວກເຮົາ ກຳ ລັງຈະເອົາເລກຈາກແຖວທີ່ ກຳ ນົດໄວ້ໃນແຕ່ລະຄັ້ງ. ພວກເຮົາຈະເລີ້ມວົງຈອນ ສຳ ລັບອົງປະກອບໃດ ໜຶ່ງ ໂດຍສະເພາະ. ໃນວົງຈອນ, ພວກເຮົາຈະສືບຕໍ່ແບ່ງປັນອົງປະກອບປັດຈຸບັນໂດຍ 2 ແລະປັບປຸງມັນໃນອົງປະກອບນັ້ນເອງ. ສິ່ງນີ້ຈະສືບຕໍ່ໄປຈົນກ່ວາປັດຈຸບັນນີ້ບໍ່ພົບວ່າມັນເປັນສິ່ງແປກ. ເວລາທີ່ເລກຈະກາຍເປັນຄີກົ້, ພວກເຮົາແຍກອອກນອກວົງຈອນ.

ສຳ ລັບຄວາມວຸ້ນວາຍຂອງແຕ່ລະອົງປະກອບຂອງອາເລ, ຊຸກຍູ້ຜົນທີ່ອອກມາ divArray ອາເລ, ບ່ອນທີ່ມັນກາຍເປັນຄີກ. ເຊັ່ນວ່າມັນຈະມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂບວນການດັ່ງທີ່ມີຢູ່ໃນອາເລທີ່ ກຳ ນົດໄວ້. ແຕ່ວ່າທຸກສ່ວນຂອງພະແນກມີຢູ່ໃນພະແນກການ. ຫຼັງຈາກການສ້າງ ສຳ ເລັດແລ້ວ, ຮຽງແຖວອາຄານທີ່ພະນັກງານແບ່ງປັນທັງ ໝົດ ຖືກເກັບໄວ້. ດັ່ງນັ້ນ, ອາເລ divArray ເຊິ່ງເກັບຮັກສາຄຸນຄ່າທັງ ໝົດ ແມ່ນຕົວເລກ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະ ດຳ ເນີນງານ XOR ກ່ຽວກັບຄ່າ divArray. ພວກເຮົາ ກຳ ລັງຈະຜ່ານ 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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ແລະ ແມ່ນຕົວເລກທີ່ມີຢູ່ໃນ log log ມີຖານ 2. log n ປັດໄຈແມ່ນຍ້ອນວ່າການແບ່ງ ຈຳ ນວນຈົນກວ່າພວກເຮົາຈະໄດ້ຮັບ divisor ຄີກ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N) ບ່ອນທີ່ "N" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ພວກເຮົາໄດ້ ນຳ ໃຊ້ອາເລເພື່ອເກັບຄ່າຂອງ xor ເຊິ່ງ ກຳ ລັງມີບ່ອນຫວ່າງຢູ່.