अवधारणा
एक दी गई पूर्णांकों की सरणी के संबंध में, हमारा कार्य एक पूर्णांक B निर्धारित करना है जो दिए गए सरणी में ठीक एक तत्व को छोड़कर सभी का भाजक है।
यह ध्यान दिया जाना चाहिए कि सभी तत्वों का GCD 1 नहीं है।
इनपुट
arr[] = {8, 16, 4, 24}आउटपुट
8 8, 4 को छोड़कर सभी का भाजक है।
इनपुट
arr[] = {50, 15, 40, 41}आउटपुट
5 5, 41 को छोड़कर सभी का भाजक है।
विधि
हम एक प्रीफिक्स सरणी A बनाते हैं जैसे कि स्थिति या इंडेक्स i में 1 से i तक के सभी तत्वों का GCD होता है। इसी तरह, एक सफ़िक्स सरणी C बनाएं जैसे कि इंडेक्स 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; // फ़ंक्शन जो सरणी में ठीक एक तत्व को छोड़कर // सभी के भाजक को लौटाता है। int getDivisor1(int a1[], int n1){ // यदि सरणी में केवल एक तत्व है if (n1 == 1) return (a1[0] + 1); int A[n1], C[n1]; // अब GCD की प्रीफिक्स सरणी बनाएं A[0] = a1[0]; for (int i = 1; i < n1; i++) A[i] = __gcd(a1[i], A[i - 1]); // अब GCD की सफ़िक्स सरणी बनाएं C[n1-1] = a1[n1-1]; for (int i = n1 - 2; i >= 0; i--) C[i] = __gcd(A[i + 1], a1[i]); // सरणी के माध्यम से पुनरावृति करने के लिए उपयोग किया जाता है for (int i = 0; i <= n1; i++) { // भाजक संग्रहीत करने के लिए वेरिएबल दिखाता है int cur1; // अब भाजक प्राप्त करना 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]); // जांचने के लिए उपयोग किया जाता है कि यह a[i] का भाजक नहीं है if (a1[i] % cur1 != 0) return cur1; } return 0; } // ड्राइवर कोड int main(){ int a1[] = { 50,15,40,41 }; int n1 = sizeof(a1) / sizeof(a1[0]); cout << getDivisor1(a1, n1); return 0; }आउटपुट
5
