HackerEarth Unique Subarrays problem solution

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.

#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("%lldn", ans);
    }
    assert(S<=100000);
    return 0;
}

HackerEarth Unique Subarrays problem solution.

Second solution

Leave a Reply