In this HackerEarth Unique Subarrays problem solution, A contiguous subarray is defined as unique if all the integers contained within it occur exactly once. There is a unique weight associated with each of the subarrays. Unique weight for any subarray equals its length if it's unique, 0 otherwise. Your task is to calculate the sum of unique weights of all the contiguous subarrays contained within a given array.


HackerEarth Unique Subarrays problem solution


HackerEarth Unique Subarrays problem solution.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#define MAX 100005
#include <cassert>
#define lli long long

using namespace std;

int A[MAX];

int main()
{
int t, n, sum_n = 0, i, j;
lli ans;
set <int> s;
cin >> t;
assert(t >= 1 && t <= 100000);
while ( t-- ) {
s.clear();
cin >> n;
sum_n += n;
ans = 0;
assert(n >= 1 && n <= 100000);
assert(sum_n >= 1 && sum_n <= 100000);
for ( int i = 0; i < n; i++ ) {
cin >> A[i];
assert(A[i] >= 1 && A[i] <= 1000000000);
}
i = 0, j = 0;
while ( i < n ) {
while ( j < n && s.find(A[j]) == s.end() ) {
s.insert(A[j]);
j++;
}
ans += (1LL*(j - i)*(j - i + 1))/2;
s.erase(A[i]);
i++;
}
cout << ans << endl;
}
return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int T, N;

int main()
{
scanf("%d", &T);
assert(1<=T && T<=100000);
int S=0;
while(T--)
{
scanf("%d", &N);
assert(1<=N && N<=100000);
S+=N;
vector<int> A(N);
for(int i=0; i<N; i++)
{
scanf("%d", &A[i]);
assert(0<=A[i] && A[i]<=1000000000);
}
long long ans=0;
set<int> s;
for(int i=0, j=0; i<N; i++)
{
for(; j<N && !s.count(A[j]); j++)
s.insert(A[j]);
ans+=1LL*(j-i)*(j-i+1)/2;
s.erase(A[i]);
}
printf("%lld\n", ans);
}
assert(S<=100000);
return 0;
}