N 정수의 배열과 범위의 Q 쿼리가 제공됩니다. 각 쿼리에 대해 범위에 있는 각 숫자의 최대 홀수 제수의 XOR을 반환해야 합니다.
최대 홀수 제수는 숫자 N을 나눌 수 있는 최대 홀수입니다. 예를 들어 6의 최대 홀수 약수는 3입니다.
Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
Output:
query1: 7
query2: 1
Explanation: greatest odd divisors of nums array are { 3, 3, 7, 5 }.
For query 1 we need to find the XOR of indexes 0, 1, and 2 which is 7, and for query2 we need to find XOR of indexes 1, 2, and 3 which is 1. 해결책을 찾기 위한 접근 방식
간단한 접근
먼저 간단한 접근 방식에서 모든 배열 요소의 최대 홀수 제수를 찾아야 합니다. 그런 다음 쿼리의 범위에 따라 범위 내 각 요소의 XOR을 계산하여 반환해야 합니다.
효율적인 접근
이 문제를 해결하는 효율적인 방법은 범위에 있는 각 숫자의 XOR을 찾을 때마다 접두사 XOR[R] - prefix_XOR[L-1 ].
접두사 xor 배열은 각 요소에 이전 요소의 xor가 모두 포함된 배열입니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int nums[] = { 3, 6, 7, 10 };
int n = sizeof(nums) / sizeof(nums[0]);
int prefix_XOR[n];
// creating an array
// containing Greatest odd divisor of each element.
for (int i = 0; i < n; i++) {
while (nums[i] % 2 != 1)
nums[i] /= 2;
prefix_XOR[i] = nums[i];
}
// changing prefix_XOR array to prefix xor array.
for (int i = 1; i < n; i++)
prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
// query array to find result of these queries.
int query[2][2] = {{0, 2},{1, 3}};
int q = sizeof(query) / sizeof(query[0]);
// finding results of queries.
for(int i = 0;i<q;i++){
if (query[i][0] == 0)
cout<< prefix_XOR[query[i][1]] << endl;
else{
int result = prefix_XOR[query[0][1]] ^ prefix_XOR[query[i][0] - 1];
cout << result << endl;
}
}
return 0;
} 출력
7 4
위 코드 설명
-
접두사_XOR 배열은 각 요소의 최대 홀수 제수를 저장하기 위해 생성되며 이 배열을 접두사 XOR 배열로 변경합니다.
-
최대 홀수 제수는 모듈로 2가 1이 될 때까지 2로 나누어 계산됩니다.
-
접두사 xor 배열은 배열을 순회하고 현재 요소와 이전 요소의 비트 XOR을 수행하여 생성됩니다.
-
쿼리 결과는 prefix_XOR[] 배열의 오른쪽 인덱스와 prefix_XOR[] 배열의 (왼쪽 - 1) 인덱스를 빼서 계산합니다.
결론
이 튜토리얼에서는 주어진 배열의 범위에서 각 숫자의 최대 홀수 제수의 XOR을 찾아야 하는 문제에 대해 논의했습니다. 우리는 각 요소의 최대 홀수 제수를 찾고 접두사 xor 배열을 사용하여 이 문제를 해결하는 방법에 대해 논의했습니다. 우리는 또한 C, Java, Python 등과 같은 프로그래밍 언어로 할 수 있는 이 문제에 대한 C++ 프로그램에 대해 논의했습니다. 이 기사가 도움이 되기를 바랍니다.