เพิ่มจำนวนอาร์เรย์ย่อยให้สูงสุดด้วย XOR เป็นศูนย์ใน C++

เราได้รับอาร์เรย์ Arr[] ที่มีค่าจำนวนเต็ม เป้าหมายคือการหาจำนวนสูงสุดของอาร์เรย์ย่อยที่มี XOR เป็น 0 บิตของอาร์เรย์ย่อยใดๆ สามารถสลับจำนวนครั้งได้

หมายเหตุ:- 1<=Arr[i]<=10 ¹⁸

ในการทำให้ XOR ของ subarray เป็น 0 โดยการแลกเปลี่ยนบิต ต้องเป็นไปตามเงื่อนไขสองประการ:-

• หากจำนวนบิตที่ตั้งไว้ในช่วงจากซ้ายไปขวาเป็นคู่

• สำหรับผลรวมของช่วงใดๆ ของบิต <=2 (จำนวนมากที่สุดในชุดบิต)

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ใน −Arr[] ={ 1,2,5,4 }

ออก −

Subarrays เป็นไปตามเงื่อนไขที่ 1 เท่านั้น :4

Subarrays เป็นไปตามเงื่อนไขทั้งสองข้อ :3

ใน − Arr[] ={ 3,7,2,9 }

ออก −

Subarrays เป็นไปตามเงื่อนไขที่ 1 เท่านั้น :6

Subarrays เป็นไปตามเงื่อนไขทั้งสองข้อ :3

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราสังเกตว่าในการที่จะทำให้ XOR ของ subarray เป็น 0 โดยการแลกเปลี่ยนบิต จะต้องเป็นไปตามเงื่อนไขสองประการ:- หากจำนวนของชุดบิตในช่วงจากซ้ายไปขวาเป็นคู่ หรือสำหรับผลรวมของช่วงใดๆ ของบิต <=2 (จำนวนมากที่สุดในเซตบิต)

• นำอาร์เรย์อินพุต Arr[] และคำนวณความยาว

• ฟังก์ชัน removeSubarr(int arr[], int len) คืนค่าจำนวนของ subarray ที่ไม่ตรงตามเงื่อนไข 2

• นับเริ่มต้นเป็น 0

• วนซ้ำอาร์เรย์โดยใช้ for loop และรับตัวแปร sum และ maxVal

• ใช้ลูปอื่นเพื่อวนซ้ำในช่วง 60 อาร์เรย์ย่อยเนื่องจากเกิน 60 เงื่อนไข 2 จะไม่มีวันเท็จ

• เพิ่มองค์ประกอบเพื่อผลรวมและรับค่าสูงสุดใน maxVal

• หากผลรวมเป็นคู่และ 2 * maxVal> ผลรวม การเพิ่มขึ้นจะไม่เป็นไปตามเงื่อนไข 2

• ที่ส่วนท้ายของทั้งสองลูปจะนับกลับ

• ฟังก์ชัน findSubarrays(int arr1[], int len1) รับอาร์เรย์อินพุตและความยาวและส่งคืนจำนวนอาร์เรย์ย่อยที่ตรงตามเงื่อนไขทั้งสองที่กล่าวถึงข้างต้น

• ใช้อาร์เรย์นำหน้าเพื่อคำนวณจำนวนอาร์เรย์ย่อยที่เป็นไปตามเงื่อนไข 1 เท่านั้น

• Traverse array ใช้ for loop และตั้งค่าแต่ละองค์ประกอบด้วย__builtin_popcountll(arr1[i]) ซึ่งเป็นจำนวนชุดบิตในนั้น

• เติมอาร์เรย์คำนำหน้าโดยใช้ for loop และตั้งค่า prefix[i] =prefix[i] + prefix[i - 1] โดยที่ยกเว้นองค์ประกอบแรก

• นับค่าคี่และคู่ในอาร์เรย์นำหน้า

• ตั้งค่า tmp1=( oddcount * (oddcount-1) )/2 และ tmp2=(evencount * (evencount-1) )/2 และผลลัพธ์เป็นผลรวมของทั้งสองอย่าง

• ผลลัพธ์จะเป็นผลรวมของอาร์เรย์ย่อยที่เป็นไปตามเงื่อนไข 1 เท่านั้น

• พิมพ์ผล

• ตอนนี้อัปเดตผลลัพธ์ด้วย result=result - removeSubarr(arr1, len1)

• ตอนนี้ผลลัพธ์มีอาร์เรย์ย่อยที่ตรงตามเงื่อนไขทั้งสอง

• พิมพ์ผลอีกครั้ง

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 2
int removeSubarr(int arr[], int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      int sum = 0;
      int maxVal = 0;

      for (int j = i; j < min(len, i + 60); j++){
         sum = sum + arr[j];
         maxVal = arr[j] > maxVal ? arr[j]: maxVal;

         if (sum % 2 == 0){
            if( 2 * maxVal > sum)
               { count++; }
         }
      }
   }
   return count;
}
int findSubarrays(int arr1[], int len1){
   int prefix[len1];
   int oddcount, evencount;
   int result;
   for (int i = 0; i < len1; i++)
   { arr1[i] = __builtin_popcountll(arr1[i]); }

   for (int i = 0; i < len1; i++){
      prefix[i] = arr1[i];
      if (i != 0)
         { prefix[i] = prefix[i] + prefix[i - 1]; }
      }
      oddcount = evencount = 0;
      for (int i = 0; i < len1; i++){
         if (prefix[i] % 2 == 0)
            { evencount = evencount +1; }
         else
            { oddcount = oddcount +1; }

      }
      evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

ผลลัพธ์

หากเรารันโค้ดข้างต้น มันจะสร้าง Out

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3