ข้อความค้นหาเกี่ยวกับ XOR ของตัวหารคี่ที่ยิ่งใหญ่ที่สุดของช่วง  


ระดับความยาก กลาง
ถามบ่อยใน ห้องทดลองนวัตกรรม 24 * 7 ป้อมปราการ Directi Expedia Google จริง Snapdeal
แถว เกร็ด Bitwise-XOR ปัญหาการสืบค้น

คำชี้แจงปัญหา  

ปัญหา“ การสืบค้นเกี่ยวกับ XOR ของตัวหารคี่ที่ยิ่งใหญ่ที่สุดของช่วง” ระบุว่าคุณได้รับไฟล์ แถว 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 ของตัวหารคี่ที่ยิ่งใหญ่ที่สุดของช่วงหมุด

 

ขั้นตอนวิธี  

  1. สำรวจอาร์เรย์ที่กำหนด
    1. หมั่นตรวจสอบองค์ประกอบปัจจุบันของอาร์เรย์หากเป็นเลขคี่และอัปเดตองค์ประกอบปัจจุบันด้วยหมายเลขตัวหารน้อยที่สุด
    2. ตั้ง divArray องค์ประกอบขององค์ประกอบการปรับปรุงของอาร์เรย์ที่กำหนด
  2. สำรวจอาร์เรย์อีกครั้งและอัปเดตแต่ละองค์ประกอบของ divArray อาร์เรย์ไปยัง XOR ขององค์ประกอบปัจจุบันและองค์ประกอบก่อนหน้าของอาร์เรย์ divArray
  3. ตรวจสอบว่าองค์ประกอบด้านซ้ายเท่ากับ 0 หรือไม่จากนั้นส่งคืน divArray [ขวา]
  4. ไม่ให้ส่งคืน XOR ของ divArray [ขวา] และ divArray [ซ้าย-1]

คำอธิบาย

เราได้ให้อาร์เรย์ของจำนวนเต็มและแบบสอบถามบางอย่างเพื่อแก้ปัญหา จากนั้นเราจะขอให้หา XOR ของตัวหารคี่ที่ยิ่งใหญ่ที่สุด แบบสอบถามประกอบด้วยจำนวนเต็มสองจำนวน หมายความว่าเรามีช่วงภายในจำนวนเต็มสองจำนวนนั้น สำหรับสิ่งนี้ก่อนอื่นเราจะหาตัวหารทั้งหมดของแต่ละจำนวนในขณะที่ข้ามอาร์เรย์ จากนั้นเราจะรับหมายเลขจากอาร์เรย์ที่กำหนดในแต่ละครั้ง เราจะเริ่มลูปสำหรับองค์ประกอบที่กำหนดโดยเฉพาะ ในลูปเราจะแบ่งองค์ประกอบปัจจุบันด้วย 2 ต่อไปและอัปเดตในองค์ประกอบนั้นเอง สิ่งนี้จะดำเนินต่อไปจนกว่าจะไม่พบว่าองค์ประกอบปัจจุบันเป็นเลขคี่ เวลาที่ตัวเลขจะกลายเป็นเลขคี่เราทำลายนอกวง

ดูสิ่งนี้ด้วย
ผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะ

สำหรับการส่งผ่านแต่ละครั้งของทุกองค์ประกอบของอาร์เรย์ให้ผลักผลลัพธ์เข้าไป divArray อาร์เรย์ที่มันกลายเป็นคี่ ดังนั้นจะมีองค์ประกอบที่เท่ากันในอาร์เรย์เช่นเดียวกับที่มีอยู่ในอาร์เรย์ที่กำหนด แต่ตัวหารทั้งหมดอยู่ใน 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 บันทึก n) ที่ไหน “ N” คือจำนวนองค์ประกอบในอาร์เรย์ และ คือตัวเลขที่มีอยู่ในบันทึกอาร์เรย์มีฐาน 2 ปัจจัยบันทึก n เป็นเพราะการหารจำนวนจนกว่าเราจะได้ตัวหารคี่

ดูสิ่งนี้ด้วย
ขั้นต่ำการย้ายไปยัง Equal Array Elements Leetcode Solution

ความซับซ้อนของอวกาศ

บน) ที่ไหน “ N” คือจำนวนองค์ประกอบในอาร์เรย์ เราได้ใช้อาร์เรย์เพื่อเก็บค่า xor ซึ่งใช้พื้นที่