এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার সাইজ n এবং দুটি ইন্টিজার a এবং b। আমাদের কাজ হল b বার থাকা একমাত্র এলিমেন্ট বের করা।
অ্যারের সব ভ্যালু a বার আছে ছাড়া একটি ভ্যালু যা b বার আছে। সেটি বের করতে হবে।
উদাহরণ দেখি:
ইনপুট
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3
আউটপুট
5
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হল প্রতিটি এলিমেন্টের অকারেন্স কাউন্ট করে ২ডি ম্যাট্রিক্সে স্টোর করা। তারপর ম্যাট্রিক্স ট্রাভার্স করে b ফ্রিকোয়েন্সি থাকা ভ্যালু বের করা।
টাইম কমপ্লেক্সিটি O(N2)। আরও দক্ষ পদ্ধতি হল অ্যারের সব ইউনিক এলিমেন্টের যোগফল বের করে 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
