हमें पूर्णांक प्रकार के तत्वों की एक सरणी दी गई है। कार्य है सरणी से जोड़े बनाना और उनके योग की गणना करके जांचना कि वह 4 से विभाज्य है या नहीं।
इनपुट - int arr[] = {4,1,2,0,2}
आउटपुट - योग 4 से विभाज्य जोड़ों की संख्या: 2
उपयोग किया गया दृष्टिकोण (नाइव)
- सरणी इनपुट करें और आकार ज्ञात करें।
- दो नेस्टेड लूप से सभी जोड़े जांचें।
- यदि
(arr[i] + arr[j]) % 4 == 0तो काउंट बढ़ाएं।
कुशल दृष्टिकोण (मॉड्यूलो 4 फ्रीक्वेंसी)
सभी तत्वों के मॉड्यूलो 4 की फ्रीक्वेंसी गिनें:
freq[0]- 4 से विभाज्य संख्याएंfreq[1]- शेष 1 देने वालीfreq[2]- शेष 2 देने वालीfreq[3]- शेष 3 देने वाली
वैध जोड़े: (0,0), (2,2), (1,3)
कुल = freq[0]*(freq[0]-1)/2 + freq[2]*(freq[2]-1)/2 + freq[1]*freq[3]
उदाहरण (नाइव दृष्टिकोण)
#include <iostream>
using namespace std;
int pair_4(int arr[], int size) {
int count = 0;
for (int i = 0; i < size; i++) {
for (int j = i+1; j < size; j++) {
if ((arr[i] + arr[j]) % 4 == 0) count++;
}
}
return count;
}
int main() {
int arr[] = {4,1,2,0,2};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count pairs in array whose sum is divisible by 4 are: " << pair_4(arr, size);
return 0;
} आउटपुट
Count pairs in array whose sum is divisible by 4 are: 2
उदाहरण (कुशल दृष्टिकोण)
#include <iostream>
using namespace std;
int pair_4(int arr[], int size) {
int freq[4] = {0};
for (int i = 0; i < size; i++)
freq[arr[i] % 4]++;
int count = freq[0] * (freq[0] - 1) / 2;
count += freq[2] * (freq[2] - 1) / 2;
count += freq[1] * freq[3];
return count;
}
int main() {
int arr[] = {4,1,2,0,2};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count pairs in array whose sum is divisible by 4 are: " << pair_4(arr, size);
return 0;
} आउटपुट
Count pairs in array whose sum is divisible by 4 are: 2