The following challenge was given the uniqueness of an array of integers is defined as the number of distinct element present for example the uniqueness of 1, 5 ,2, 1, 3, 5 is 4 element value 1 ,2, 3 and 5 for an array arr of an integers the uniqueness value of its generated and stored in another array call array_uniqueness for discussion find the median of The generated array_uniqueness notes the median of the of a list is defined as the middle value of the list when it is sorted in non decreasing order if there are multiple choices for median the smaller of the two value is taken for example the median of 1, 5, 8 is 5 and of 2 ,3 ,7, 11 is 3 second point A sub array is a contagious part of the array
There are n=3 elements in arr=[1,2,1]
The subaarrau along with their uniquness values are:
[1]: uniqueness=1
[1,3]: uniqumess =2
[1,2,1] uniqiness =2
[2] uniqiness =1
[2,1] uniqiness =2
[1] uniqiness =2
#define ll long long
ll count_sub(ll k, map<int, int>& m, vector<int>& arr){
m.clear();
ll res = 0;
int i=0, j=0, n = arr.size();
while(j<n){
m[arr[j]]++;
j++;
while(m.size() > k){
m[arr[i]]--;
if(m[arr[i]] == 0){
m.erase(arr[i]);
}
i++;
}
res += (j-i);
}
return res;
}
int findMedianOfSubarrayUniqueness(vector<int> arr) {
ll n = arr.size();
ll sub_count = n*(n+1)/2;
ll req = (sub_count+1)/2;
map<int, int> m;
for(auto i: arr){
m[i]++;
}
ll l = 1, r = m.size();
while(l<=r){
ll mid = l + (r-l)/2;
ll curr = count_sub(mid, m, arr);
if(curr >= req){
r = mid - 1;
ll prev = count_sub(mid-1, m, arr);
if(prev < req || mid == 1) return mid;
}else{
l = mid + 1;
}
}return 0;
}