배열이 주어지고 비어 있지 않은 적어도 하나의 하위 배열의 비트 AND인 모든 가능한 정수를 찾아야 하는 문제를 해결하려면 -
Input : nums[ ] = { 3, 5, 1, 2, 8 }
Output : { 2, 5, 0, 3, 8, 1 }
Explanation:
2 is the bitwise AND of subarray {2},
5 is the bitwise AND of subarray {5},
0 is the bitwise AND of subarray {1, 2}, {2, 8} and {1, 2, 8},
3 is the bitwise AND of subarray {3},
8 is the bitwise AND of subarray {8},
1 is the bitwise AND of subarray {1}, {3, 5} and {3, 5, 1}.
Input : nums[ ] = { 2, 6, 3, 8, 1 }
Output: { 1, 8, 3, 6, 2, 0 } 해결책을 찾기 위한 접근 방식
간단한 접근 방식 적용할 수 있는 것은
-
비어 있지 않은 가능한 모든 하위 배열을 찾습니다.
-
배열을 탐색하는 동안 하위 배열의 각 요소에 대한 비트 AND를 계산합니다.
-
중복 값을 방지하려면 모든 결과를 집합에 저장하십시오.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] ={ 2, 6, 3, 8, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Declaring set to store result of each AND operation.
unordered_set<int> result;
int val;
// nested loops to traverse through all the possible non empty subarrays.
for (int i = 0; i < n; ++i){
for (int j = i, val = INT_MAX; j < n; ++j){
val = val & arr[j];
// storing result of AND operation
result.insert(val);
}
}
cout << "All possible numbers are: ";
// printing all the values of set.
for (auto i = result.begin(); i != result.end();i++)
cout << *i << " ";
return 0;
} 출력
All possible numbers are: 1 8 3 6 0 2
위 코드 설명
-
AND 연산의 모든 결과를 저장하도록 집합을 선언합니다.
-
모든 비트를 1로 설정한 상태에서 AND 연산을 수행해야 하므로 INT_MAX로 'val' 변수를 초기화합니다.
-
i번째 인덱스에서 가능한 모든 하위 배열을 통과하는 내부 루프.
-
각 요소의 AND 연산을 서로 및 자체적으로 계산하여 결과 집합에 저장합니다.
-
결과 집합의 모든 값을 인쇄합니다.
결론
이 자습서에서는 이 문제를 해결하기 위한 간단한 접근 방식, 즉 가능한 모든 하위 배열에서 AND 연산을 계산하는 방법에 대해 논의했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램에 대해 논의했습니다. 또한 이 코드는 Java, C, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.