# HackerEarth Shubham and Subarrays problem solution

In this HackerEarth Shubham and Subarrays problem solution You are given an array consisting of n integer numbers a1,a2..an. Two subarrays  ([l1,r1]) (1 <= l1 <= r1 <= n) and [l2,r2] (1 < l2 <= r2 <= n) are considered the same if they have the same "special set" of numbers. Output the number of distinct subarrays.
Note: A "special set" of numbers is a set of unique numbers sorted in increasing order.For example,the "special set" corresponding to the numbers [5,2,7,2,5,9] is [2,5,7,9].

## HackerEarth Shubham and Subarrays problem solution.

`#include <iostream>#include<bits/stdc++.h>using namespace std;#define ll long long int#define inf 1000000000000#define mod 1000000007#define pb push_back#define mp make_pair#define all(v) v.begin(),v.end()#define S second#define F first#define boost1 ios::sync_with_stdio(false);#define boost2 cin.tie(0);#define mem(a,val) memset(a,val,sizeof a)#define endl "\n"#define maxn 1005ll arr[maxn],power1[maxn],power2[maxn],seen[maxn],base1=127,base2=129,mod1=mod,mod2=mod+2;set<pair<ll,ll> >s;inline ll add(ll x,ll y,ll modulus){    x+=y;    if(x>=modulus)    x-=modulus;    return x;}inline ll mul(ll x,ll y,ll modulus){    return (x*y)%modulus;}int main(){    boost1;boost2;    ll i,j,n,x,y,hash_val1,hash_val2;    power1[0]=1;    power2[0]=1;    for(i=1;i<=1000;i++)    {        power1[i]=mul(power1[i-1],base1,mod1);        power2[i]=mul(power2[i-1],base2,mod2);    }    cin>>n;    for(i=1;i<=n;i++)    cin>>arr[i];    for(i=1;i<=n;i++)    {        hash_val1=0;        hash_val2=0;        for(j=i;j<=n;j++)        {            if(!seen[arr[j]])            {                hash_val1=add(hash_val1,power1[arr[j]],mod1);                hash_val2=add(hash_val2,power2[arr[j]],mod2);            }            seen[arr[j]]=1;            s.insert({hash_val1,hash_val2});        }        for(j=i;j<=n;j++)        seen[arr[j]]=0;    }    cout<<s.size();    return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define ll long long#define ii pair<int, int>#define ff first #define ss second int temp[1005];int main(){    int i, j, n, base[2], mod[2], arr[1005], ans = 0;    int pwrs[2][1005];    base[0] = 31;   mod[0] = 999999937;    base[1] = 37;   mod[1] = 999999929;    unordered_map<ll, bool> globe;    pwrs[0][0] = 1;    pwrs[1][0] = 1;    for(i = 1; i <= 1000; i++){        pwrs[0][i] = (1ll * pwrs[0][i - 1] * base[0]) % mod[0];        pwrs[1][i] = (1ll * pwrs[1][i - 1] * base[1]) % mod[1];    }    scanf("%d", &n);    for(i = 0; i < n; i++)        scanf("%d", &arr[i]);    for(i = 0; i < n; i++){        ii curr = {0, 0};        for(j = i; j < n; j++){            if(temp[arr[j]] != 0)                continue;            temp[arr[j]] = 1;            curr.ff = (curr.ff + pwrs[0][arr[j]]) % mod[0];            curr.ss = (curr.ss + pwrs[1][arr[j]]) % mod[1];            if(globe[((1ll * curr.ff) << 30) + curr.ss] != 0)                continue;            ans++;            globe[((1ll * curr.ff) << 30) + curr.ss] = 1;        }        for(j = i; j < n; j++)            temp[arr[j]] = 0;    }    printf("%d\n", ans);    return 0;}`