এই সমস্যায়, আমাদের 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 দ্বারা গুণ করা। তারপর এই মান থেকে পুরো অ্যারের যোগফল বিয়োগ করুন এবং তারপর ফলাফলটিকে (a-b) দ্বারা ভাগ করুন। ফলের মান হল সেই মান যার সংঘটন ফ্রিকোয়েন্সি 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
