ধারণা
প্রদত্ত পূর্ণসংখ্যার বিন্যাসের ক্ষেত্রে, আমাদের কাজ হল একটি পূর্ণসংখ্যা 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.
পদ্ধতি
আমরা একটি প্রিফিক্স অ্যারে A তৈরি করি যাতে অবস্থান বা সূচক i 1 থেকে i পর্যন্ত সমস্ত উপাদানের GCD ধারণ করে। একইভাবে, একটি প্রত্যয় অ্যারে সি তৈরি করুন যাতে সূচক i তে i থেকে n-1 (শেষ সূচক) পর্যন্ত সমস্ত উপাদানের GCD থাকে। এটা দেখা গেছে যে 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
