সর্টেড অ্যারে — উপাদানগুলো আরোহী বা অবরোহী ক্রমে সাজানো।
এবসোলিউট ডিস্টিংক্ট কাউন্ট — প্রতিটি উপাদানের নিরপেক্ষ মান (absolute value) নিলে কতগুলো ডISTINCT মান থাকে।
উদাহরণ
Input: [-3, 0, 3, 6] Output: 3 (ডিস্টিংক্ট: 0, 3, 6)
পদ্ধতি ১: Set ব্যবহার
- প্রতিটি উপাদানের
abs()নিয়ে set-এ ইনসার্ট করুন। - সেটের সাইজ = ডিস্টিংক্ট কাউন্ট।
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {-3, 0, 2, 6};
int n = sizeof(arr)/sizeof(arr[0]);
unordered_set<int> s;
for (int i = 0; i < n; i++) s.insert(abs(arr[i]));
cout << "Count of absolute distinct values : " << s.size();
return 0;
}
Count of absolute distinct values : 4
পদ্ধতি ২: টু-পয়েন্টার (O(1) স্পেস)
সর্টেড অ্যারে থাকায় দুটি পয়েন্টার i (শুরু) এবং j (শেষ) দিয়ে কাজ করা যায়।
#include <iostream>
using namespace std;
int main() {
int arr[] = {-5, -1, 0, 5, 8};
int n = sizeof(arr)/sizeof(arr[0]);
int count = n, i = 0, j = n-1, sum = 0;
while (i < j) {
while (i != j && arr[i] == arr[i+1]) count--, i++;
while (i != j && arr[j] == arr[j-1]) count--, j--;
if (i == j) break;
sum = arr[i] + arr[j];
if (sum == 0) { count--; i++; j--; }
else if (sum < 0) i++;
else j--;
}
cout << "Count of absolute distinct values : " << count;
return 0;
}
Count of absolute distinct values : 4
