আমাদের ১ থেকে n রেঞ্জের এলিমেন্ট ধারণকারী একটি অ্যারে দেওয়া আছে। কিছু এলিমেন্ট রিপিট, কিছু মিসিং। লক্ষ্য O(n) টাইম এবং O(1) এক্সট্রা স্পেসে সব এলিমেন্টের ফ্রিকোয়েন্সি বের করা।
ইনপুট
Arr[]= { 1,2,2,3,4,4,4,5 }
আউটপুট
1→ 1, 2 → 2, 3→ 1, 4→ 3, 5→ 1
ইনপুট
Arr[]= { 1,4,4,5,5,5,5 }
আউটপুট
1→ 1, 2 → 0, 3→ 0, 4→ 2, 5→ 4
প্রোগ্রামে ব্যবহৃত পদ্ধতি (১ থেকে ১০ রেঞ্জের জন্য)
- printfrequency(int arr[], int n) ফাংশন।
- arr[i] = arr[i] - 1 করে ০-বেসড করা (১ ইনডেক্স ০, ২ ইনডেক্স ১...)।
- for i=0 to n-1: arr[arr[i]%10] += 10 (কারণ সংখ্যা ১-১০, মড ১০ = নিজের মান)۔
- একটি সংখ্যা x বার থাকলে arr[সেটি-১]-এ ১০ x বার যোগ হবে।
- শেষে arr[i]/10 দিয়ে ফ্রিকোয়েন্সি প্রিন্ট (i+1 এর জন্য)۔
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
void printfrequency(int arr[], int n){
for (int i = 0; i < n; i++) arr[i] = arr[i] - 1;
for (int i = 0; i < n; i++) arr[arr[i] % 10] += 10;
for (int i = 0; i < 10; i++) cout << i + 1 << " -> " << arr[i]/10 << endl;
}
int main(){
int arr[] = {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9};
int n = sizeof(arr)/sizeof(arr[0]);
printfrequency(arr, n);
return 0;
}আউটপুট
1 -> 0 2 -> 2 3 -> 2 4 -> 0 5 -> 1 6 -> 1 7 -> 3 8 -> 2 9 -> 5 10 -> 0
