Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 XOR을 0으로 사용하여 하위 배열 수 최대화

<시간/>

정수 값을 포함하는 배열 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