HackerEarth Shubham and Subarrays problem solution YASH PAL, 31 July 2024 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("%dn", ans); return 0;} coding problems