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

C++ में सरणी में योग k से विभाज्य जोड़े गिनना


हमें पूर्णांक प्रकार के तत्वों की एक सरणी दी गई है। कार्य है सरणी से जोड़े बनाना और उनके योग की गणना करके जांचना कि वह k से विभाज्य है या नहीं।

इनपुट - int arr[] = {4,1,2,0,2}, k = 2

आउटपुट - योग k से विभाज्य जोड़ों की संख्या: 6

उपयोग किया गया दृष्टिकोण (नाइव)

  • सरणी और k इनपुट करें।
  • दो नेस्टेड लूप से सभी जोड़े जांचें।
  • यदि (arr[i] + arr[j]) % k == 0 तो काउंट बढ़ाएं।

कुशल दृष्टिकोण (मॉड्यूलो फ्रीक्वेंसी)

सभी तत्वों के arr[i] % k की फ्रीक्वेंसी गिनें। फिर:

  • शेष 0 वाले: freq[0] * (freq[0]-1) / 2
  • शेष i और k-i वाले: freq[i] * freq[k-i] (i = 1 से k/2 तक)
  • यदि k सम है: freq[k/2] * (freq[k/2]-1) / 2

समय जटिलता: O(n + k)

उदाहरण (नाइव दृष्टिकोण)

#include <iostream> 
using namespace std; 

int pair_k(int arr[], int size, int k) { 
    int count = 0; 
    for (int i = 0; i < size; i++) { 
        for (int j = i+1; j < size; j++) { 
            int sum = arr[i] + arr[j]; 
            if (sum % k == 0) count++; 
        } 
    } 
    return count; 
} 

int main() { 
    int arr[] = {4,1,2,0,2}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int k = 2; 
    cout << "Count pairs in array whose sum is divisible by k are: " << pair_k(arr, size, k); 
    return 0; 
}

आउटपुट

Count pairs in array whose sum is divisible by k are: 6

उदाहरण (कुशल दृष्टिकोण)

#include <iostream> 
using namespace std; 

int pair_k(int arr[], int size, int k) { 
    vector<int> freq(k, 0); 
    for (int i = 0; i < size; i++) 
        freq[arr[i] % k]++; 
    int count = freq[0] * (freq[0] - 1) / 2; 
    for (int i = 1; i <= k/2 && i != k-i; i++) 
        count += freq[i] * freq[k-i]; 
    if (k % 2 == 0) 
        count += freq[k/2] * (freq[k/2] - 1) / 2; 
    return count; 
} 

int main() { 
    int arr[] = {4,1,2,0,2}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int k = 2; 
    cout << "Count pairs in array whose sum is divisible by k are: " << pair_k(arr, size, k); 
    return 0; 
}

आउटपुट

Count pairs in array whose sum is divisible by k are: 6

  1. - C++ में दिए गए सरणी में मौजूद योग वाले विशिष्ट जोड़ों की संख्या गिनें

    हमें एक सरणी दी गई है, मान लीजिए arr[] किसी भी संबंधित आकार के पूर्णांक मानों की और कार्य दिए गए सरणी में उपलब्ध विशिष्ट जोड़ों की संख्या की गणना करना है जिनका योग उसी सरणी में मौजूद है। याद रखने योग्य बिंदु एक जोड़ी को समान तत्वों के साथ एक बार गिना जाएगा चाहे उनका क्रम कुछ भी हो। उदाहरण के लिए,

  1. - C++ में सरणी में विभाज्य जोड़ों की गिनती करें

    हमें किसी भी आकार की एक सरणी दी गई है जिसमें पूर्णांक तत्व हैं और कार्य सरणी में जोड़ों की संख्या की गणना करना है जैसे कि एक जोड़ी का एक तत्व जोड़ी के दूसरे तत्व को विभाजित करता है। उदाहरण के लिए इनपुट - int arr[] = {1, 2, 3, 6} आउटपुट - गिनती 4 है व्याख्या - (1,2), (1,3), (1,6) और (3,6) वे जोड़े

  1. - C++ में सरणी में मिश्रित तत्वों की गिनती और योग

    हमें सकारात्मक पूर्णांकों की एक सरणी दी गई है और कार्य दी गई सरणी में मिश्रित तत्वों की गिनती और योग की गणना करना है। मिश्रित संख्याएं क्या हैं दिए गए पूर्णांकों के समूह से, जो संख्याएं अभाज्य नहीं हैं उन्हें मिश्रित संख्याएं कहा जाता है सिवाय 1 के जो न तो मिश्रित है और न ही अभाज्य बल्कि यह एक इका