अवधारणा
दिए गए सरणी array[] के संबंध में जिसमें दूसरे सरणी के तत्वों के हर संभावित जोड़ी के GCD हैं, हमारा कार्य उन मूल संख्याओं को निर्धारित करना है जिनका उपयोग GCD सरणी की गणना के लिए किया गया था।
इनपुट
array[] = {6, 1, 1, 13}
आउटपुट
13 6 gcd(13, 13) = 13 gcd(13, 6) = 1 gcd(6, 13) = 1 gcd(6, 6) = 6
इनपुट
arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}
आउटपुट
13 11 8 6 6
विधि
सबसे पहले, सरणी को घटते क्रम में क्रमबद्ध करें।
सबसे बड़ा तत्व हमेशा मूल संख्याओं में से एक होगा। उस संख्या को बनाए रखें और इसे सरणी से हटा दें।
पिछले चरण में लिए गए तत्व का GCD वर्तमान तत्व के साथ गणना करें जो सबसे बड़े से शुरू होता है और GCD मान को दी गई सरणी से हटा दें।
उदाहरण
// दृष्टिकोण का C++ कार्यान्वयन #include <bits/stdc++.h> using namespace std; // सरणी की सामग्री प्रिंट करने के लिए उपयोगिता फ़ंक्शन दिखाता है void printArr(int array[], int n1){ for (int i = 0; i < n1; i++) cout << array[i] << " "; } // आवश्यक संख्याओं को निर्धारित करने के लिए फ़ंक्शन दिखाता है void findNumbers(int array[], int n1){ // घटते क्रम में सरणी क्रमबद्ध करने के लिए उपयोग किया जाता है sort(array, array + n1, greater<int>()); int freq1[array[0] + 1] = { 0 }; // यहां, प्रत्येक तत्व की आवृत्ति गिनें for (int i = 0; i < n1; i++) freq1[array[i]]++; // परिणामी सरणी का आकार दिखाता है int size1 = sqrt(n1); int brr1[size1] = { 0 }, x1, l1 = 0; for (int i = 0; i < n1; i++) { if (freq1[array[i]] > 0) { // परिणामी सरणी में उच्चतम तत्व संग्रहीत करें brr1[l1] = array[i]; // उस तत्व की आवृत्ति घटाएं freq1[brr1[l1]]--; l1++; for (int j = 0; j < l1; j++) { if (i != j) { // GCD की गणना करें x1 = __gcd(array[i], brr1[j]); // GCD मान को 2 से घटाएं freq1[x1] -= 2; } } } } printArr(brr1, size1); } // ड्राइवर कोड int main(){ /* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */ int array[] = { 6, 1, 1, 13}; int n1 = sizeof(array) / sizeof(array[0]); findNumbers(array, n1); return 0; }
आउटपुट
13 6
