Chúng ta được cung cấp một mảng Arr [] chứa các giá trị nguyên. Mục tiêu là tìm số lượng mảng con tối đa với XOR là 0. Các bit của bất kỳ mảng con nào có thể được hoán đổi với nhau bất kỳ số lần nào.
Lưu ý:- 1 <=Arr [i] <=10 18
Để đặt bất kỳ XOR của mảng con nào là 0 bằng cách hoán đổi các bit, hai điều kiện phải được đáp ứng:-
-
Nếu số lượng bit đã đặt trong phạm vi từ trái sang phải là số chẵn.
-
Đối với mọi dải ô đã cho, tổng số bit <=2 (số lớn nhất trong các bit đã đặt)
Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -
Trong −Arr [] ={1,2,5,4}
Hết -
Các mảng con chỉ thỏa mãn điều kiện đầu tiên:4
Các mảng con thỏa mãn cả hai điều kiện:3
Trong - Arr [] ={3,7,2,9}
Hết -
Các mảng con chỉ thỏa mãn điều kiện đầu tiên:6
Các mảng con thỏa mãn cả hai điều kiện:3
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi nhận thấy rằng để biến XOR của bất kỳ mảng con nào là 0 bằng cách hoán đổi các bit, hai điều kiện phải được đáp ứng:- Nếu số lượng bit đặt trong phạm vi từ trái sang phải là số chẵn hoặc đối với bất kỳ phạm vi nào thì tổng số bit <=2 (số lớn nhất trong các bit đã đặt)
-
Lấy mảng đầu vào Arr [] và tính độ dài của nó.
-
Hàm removeSubarr (int arr [], int len) trả về số lượng các mảng con không thỏa mãn điều kiện 2.
-
Lấy số lượng ban đầu là 0.
-
Lặp lại mảng bằng vòng lặp for và lấy các biến tổng và maxVal.
-
Lấy một vòng lặp for khác để lặp lại trong phạm vi 60 mảng con vì ngoài 60, điều kiện 2 không bao giờ có thể sai.
-
Thêm phần tử vào tổng và lấy giá trị lớn nhất trong maxVal.
-
Nếu tổng là số chẵn và 2 * maxVal> sum thì số gia tăng do điều kiện 2 không được đáp ứng.
-
Ở cuối cả hai vòng lặp, số lượng trả về.
-
Hàm findSubarrays (int arr1 [], int len1) nhận một mảng đầu vào và độ dài của nó và trả về số lượng các mảng con thỏa mãn cả hai điều kiện nêu trên.
-
Lấy một mảng tiền tố để tính toán số lượng các mảng con chỉ tuân theo điều kiện 1.
-
Traverse mảng bằng cách sử dụng vòng lặp for và đặt từng phần tử với__builtin_popcountll (arr1 [i]) là số bit đã đặt trong đó.
-
Điền mảng tiền tố bằng vòng lặp for và đặt tiền tố [i] =prefix [i] + prefix [i - 1] trong đó ngoại trừ phần tử đầu tiên.
-
Đếm các giá trị chẵn và lẻ trong mảng tiền tố.
-
Đặt tmp1 =(số lẻ * (số lẻ-1)) / 2 và tmp2 =(số tiền chẵn * (số tiền chẵn-1)) / 2 và kết quả là tổng của cả hai.
-
Kết quả sẽ chỉ là tổng của các mảng con thỏa mãn điều kiện 1.
-
In kết quả.
-
Bây giờ hãy cập nhật kết quả với result =result - removeSubarr (arr1, len1).
-
Bây giờ kết quả chứa các mảng con thỏa mãn cả hai điều kiện.
-
In lại kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra các lỗi sau
Subarrays satisfying only 1st condition : 4 Subarrays satisfying both condition : 3