समस्या विवरण
इस समस्या में, हमें आकार n की एक सरणी arr[] और दो पूर्णांक a और b दिए गए हैं। हमारा कार्य केवल B बार आने वाला तत्व खोजना है।
सरणी के सभी मान a बार आते हैं सिवाय एक मान के जो सरणी में b बार आता है और हमें उस मान को खोजने की आवश्यकता है।
उदाहरण
इनपुट
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1, 1, 1}
a = 4, b = 3
आउटपुट
5
हल का दृष्टिकोण
समस्या का एक सरल समाधान प्रत्येक तत्व की घटना को गिनना और फिर इसे 2D मैट्रिक्स में संग्रहीत करना है। फिर मैट्रिक्स को पार करके आवृत्ति b वाले मान को खोजना।
इस दृष्टिकोण की समय जटिलता O(N²) है लेकिन एक अधिक प्रभावी दृष्टिकोण जो समस्या को हल कर सकता है, वह है सरणी के सभी अद्वितीय तत्वों का योग खोजना और फिर इसे a से गुणा करना। फिर इस मान से पूरी सरणी का योग घटाएं और फिर परिणाम को (a-b) से विभाजित करें। परिणामी मान वह मान है जिसकी घटना आवृत्ति b है।
गणितीय सूत्र
मान लीजिए: - uniqueSum = सभी अद्वितीय तत्वों का योग - arrSum = सरणी के सभी तत्वों का योग - x = वह तत्व जो b बार आता है - अन्य सभी तत्व a बार आते हैं तब: arrSum = a × uniqueSum - (a - b) × x x = (a × uniqueSum - arrSum) / (a - b)
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
int findbFreqVal(int arr[], int n, int a, int b) {
unordered_set<int> uniqueVal;
int uniqueValSum = 0, arrSum = 0;
for (int i = 0; i < n; i++) {
if (uniqueVal.find(arr[i]) == uniqueVal.end()) {
uniqueVal.insert(arr[i]);
uniqueValSum += arr[i];
}
arrSum += arr[i];
}
uniqueValSum = a * uniqueValSum;
return ((uniqueValSum - arrSum) / (a - b));
}
int main() {
int arr[] = {4, 4, 4, 31, 8, 8, 8, 5, 5, 5};
int a = 3, b = 1;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "सरणी में b बार आने वाला मान है " << findbFreqVal(arr, n, a, b);
return 0;
}
आउटपुट
सरणी में b बार आने वाला मान है 31
जटिलता विश्लेषण
- समय जटिलता: O(N)
- स्पेस जटिलता: O(N) - अद्वितीय तत्वों के लिए हैश सेट
महत्वपूर्ण शर्त
यह विधि तब काम करती है जब ठीक एक तत्व की आवृत्ति b हो और अन्य सभी की आवृत्ति a हो। यह a > b मानता है।
