정수 값을 포함하는 배열 Arr[]이 제공됩니다. 목표는 XOR이 0인 하위 배열의 최대 수를 찾는 것입니다. 하위 배열의 비트는 여러 번 바꿀 수 있습니다.
참고:- 1<=Arr[i]<=10 18
비트를 교환하여 하위 배열의 XOR을 0으로 만들려면 두 가지 조건이 충족되어야 합니다.-
-
좌에서 우로 설정한 비트의 수가 짝수인 경우.
-
주어진 범위의 비트 합계 <=2(세트 비트에서 가장 큰 수)
이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -
에서 -Arr[] ={ 1,2,5,4 }
밖으로 -
첫 번째 조건만 만족하는 부분배열 :4
두 조건을 모두 만족하는 부분배열 :3
에서 - Arr[] ={ 3,7,2,9 }
밖으로 -
첫 번째 조건만 만족하는 부분배열 :6
두 조건을 모두 만족하는 부분배열 :3
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -
이 접근 방식에서 우리는 비트를 교환하여 하위 배열의 XOR을 0으로 만들기 위해 두 가지 조건이 충족되어야 함을 관찰했습니다. 2(설정 비트에서 가장 큰 수)
-
입력 배열 Arr[]을 사용하여 길이를 계산합니다.
-
함수 removeSubarr(int arr[], int len)은 조건 2를 충족하지 않는 부분배열의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
for 루프를 사용하여 배열을 반복하고 변수 sum 및 maxVal을 사용합니다.
-
조건 2는 절대 거짓일 수 없으므로 60개를 초과하는 하위 배열 범위에서 반복하려면 또 다른 for 루프를 사용하십시오.
-
합계에 요소를 추가하고 maxVal에서 최대값을 취합니다.
-
sum이 짝수이고 2 * maxVal> sum이면 조건 2로 증분 카운트가 충족되지 않습니다.
-
두 루프의 끝에서 카운트를 반환합니다.
-
findSubarrays(int arr1[], int len1) 함수는 입력 배열과 그 길이를 받아 위에서 언급한 두 가지 조건을 모두 만족하는 하위 배열의 개수를 반환합니다.
-
접두사 배열을 사용하여 조건 1만 따르는 하위 배열의 수를 계산합니다.
-
for 루프를 사용하여 배열을 순회하고 각 요소에 설정된 비트 수인 __builtin_popcountll(arr1[i])로 설정합니다.
-
for 루프를 사용하여 접두사 배열을 채우고 접두사[i] =접두사[i] + 접두사[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