इस समस्या में, हमें n आकार का arr[] और दो पूर्णांक a और b दिए गए हैं। हमारा काम f . करना है एकमात्र तत्व है जो b बार प्रकट होता है ।
सरणी के सभी मान एक बार होते हैं, केवल एक मान को छोड़कर जो सरणी में b बार होता है और हमें उस मान को खोजने की आवश्यकता होती है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3 आउटपुट
5
समाधान दृष्टिकोण
समस्या का एक सरल समाधान प्रत्येक तत्व की घटना की गणना करके और फिर इसे 2D मैट्रिक्स में संग्रहीत करना है। फिर आवृति आवृत्ति b के साथ मान ज्ञात करने के लिए मैट्रिक्स को ट्रैवर्स करना।
इस दृष्टिकोण की समय जटिलता O(N 2 . है ) लेकिन एक अधिक प्रभावी तरीका जो समस्या को हल कर सकता है, वह है सरणी के सभी अद्वितीय तत्वों का योग ज्ञात करना और फिर इसे a से गुणा करना। फिर इस मान से पूरे सरणी का योग घटाएं और फिर परिणाम को (ए-बी) से विभाजित करें। परिणामी मान वह मान है जिसकी आवृत्ति आवृत्ति b है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#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<<"The value of the array that appears b times is "<<findbFreqVal(arr, n, a, b);
return 0;
} आउटपुट
The value of the array that appears b times is 31