개념
주어진 정수 배열과 관련하여 우리의 임무는 주어진 배열에서 정확히 하나의 요소를 제외한 모든 것의 제수인 정수 B를 결정하는 것입니다.
모든 요소의 GCD가 1이 아니라는 점에 유의해야 합니다.
입력
arr[] = {8, 16, 4, 24}
출력
8 8 is the divisor of all except 4.
입력
arr[] = {50, 15, 40, 41}
출력
5 5 is the divisor of all except 41.
방법
위치 또는 인덱스 i가 1에서 i까지의 모든 요소의 GCD를 포함하도록 접두사 배열 A를 만듭니다. 비슷한 방법으로 인덱스 i가 i에서 n-1(마지막 인덱스)까지의 모든 요소의 GCD를 포함하도록 접미사 배열 C를 만듭니다. A[i-1] 및 C[i+1]의 GCD가 i에 있는 요소의 제수가 아닌 경우 필수 답인 것으로 나타났습니다.
예시
// C++ program to find the divisor of all // except for exactly one element in an array. #include <bits/stdc++.h> using namespace std; // Shows function that returns the divisor of all // except for exactly one element in an array. int getDivisor1(int a1[], int n1){ // If there's only one element in the array if (n1 == 1) return (a1[0] + 1); int A[n1], C[n1]; // Now creating prefix array of GCD A[0] = a1[0]; for (int i = 1; i < n1; i++) A[i] = __gcd(a1[i], A[i - 1]); // Now creating suffix array of GCD C[n1-1] = a1[n1-1]; for (int i = n1 - 2; i >= 0; i--) C[i] = __gcd(A[i + 1], a1[i]); // Used to iterate through the array for (int i = 0; i <= n1; i++) { // Shows variable to store the divisor int cur1; // now getting the divisor if (i == 0) cur1 = C[i + 1]; else if (i == n1 - 1) cur1 = A[i - 1]; else cur1 = __gcd(A[i - 1], C[i + 1]); // Used to check if it is not a divisor of a[i] if (a1[i] % cur1 != 0) return cur1; } return 0; } // Driver code int main(){ int a1[] = { 50,15,40,41 }; int n1 = sizeof(a1) / sizeof(a1[0]); cout << getDivisor1(a1, n1); return 0; }
출력
5