Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सरणी में अधिकतम GCD वाली जोड़ी ढूंढना


मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी है। हमारा कार्य सरणी से पूर्णांकों की जोड़ी ढूंढना है, जहां GCD मान अधिकतम है। मान लीजिए A = {1, 2, 3, 4, 5}, तो आउटपुट 2 है। जोड़ी (2, 4) का GCD 2 है, अन्य GCD मान 2 से कम हैं।

इस समस्या को हल करने के लिए, हम एक काउंट सरणी बनाए रखेंगे जो प्रत्येक तत्व के भाजकों की गिनती संग्रहीत करेगी। भाजकों की गिनती की प्रक्रिया O(sqrt(arr[i])) समय लेगी। संपूर्ण ट्रैवर्सल के बाद, हम काउंट सरणी को अंतिम इंडेक्स से पहले इंडेक्स तक ट्रैवर्स कर सकते हैं, फिर यदि हमें कोई मान मिलता है जहां तत्व 1 से अधिक है, तो इसका मतलब है कि यह 2 तत्वों का भाजक है और अधिकतम GCD भी है।

उदाहरण

#include <iostream> #include <cmath> using namespace std; int getMaxGCD(int arr[], int n) {    int high = 0;    for (int i = 0; i < n; i++)    high = max(high, arr[i]);    int divisors[high + 1] = { 0 }; //array to store all gcd values    for (int i = 0; i < n; i++) {       for (int j = 1; j <= sqrt(arr[i]); j++) {          if (arr[i] % j == 0) {             divisors[j]++;          if (j != arr[i] / j)             divisors[arr[i] / j]++;          }       }    }    for (int i = high; i >= 1; i--)    if (divisors[i] > 1)    return i; } int main() {    int arr[] = { 1, 2, 4, 8, 12 };    int n = sizeof(arr) / sizeof(arr[0]);    cout << "Max GCD: " << getMaxGCD(arr,n); }

आउटपुट

Max GCD: 4

  1. - C++ में डुप्लिकेट तत्वों वाली सरणी में फिक्स्ड पॉइंट ढूंढें

    समस्या विवरण एक क्रमबद्ध सरणी में फिक्स्ड पॉइंट वह तत्व है जिसका मान उसके सूचकांक के बराबर होता है। सरणी में नकारात्मक संख्याएं और डुप्लिकेट तत्व हो सकते हैं। यदि फिक्स्ड पॉइंट मौजूद है तो उसका मान वापस करें, अन्यथा -1 वापस करें। हल दृष्टिकोण बाइनरी खोज का उपयोग करके O(log n) समय में हल करें। डुप्

  1. - C++ में दिए गए सरणी के एलिमेंट्स के फैक्टोरियल का GCD खोजें

    मान लीजिए हमारे पास N एलिमेंट्स वाली एक सरणी A है। हमें सरणी के सभी एलिमेंट्स के फैक्टोरियल का GCD निकालना है। मान लीजिए एलिमेंट्स {3, 4, 8, 6} हैं, तो फैक्टोरियल का GCD 6 होगा। यहां हम ट्रिक देखेंगे। चूंकि दो संख्याओं का GCD वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है, तो दो संख्याओं के फैक्

  1. - C++ में दिए गए GCD और LCM के साथ कोई भी पेयर खोजें

    इस सेक्शन में हम देखेंगे कि दिए गए GCD और LCM मानों का उपयोग करके नंबर पेयर्स की संख्या कैसे प्राप्त करें। मान लीजिए GCD और LCM मान 2 और 12 हैं। अब नंबरों के संभावित पेयर्स हैं (2, 12), (4, 6), (6, 4) और (12, 2)। इसलिए हमारा प्रोग्राम पेयर्स की संख्या ढूंढेगा। वह 4 है।आइए एल्गोरिदम देखें कि इस समस्य