हमें पूर्णांक प्रकार के तत्वों की एक सरणी दी गई है। कार्य है सरणी से जोड़े बनाना और उनके योग की गणना करके जांचना कि वह 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