In this HackerEarth Distinct Digits II problem solution Andi and Bob are the best friends of each other.They both are good programmers as well,They like to do programming together so that if one finds any difficulty other can help.But these days Andi is quite busy as his exams are on the way . So, Bob has to do programming alone.while practising on HackerEarth Bob encounters an interesting problem which he was unable to solve efficiently.So, he asked for Andi's help.

Problem as stated by Bob :

we have given an array of N elements and Q queries need to be processed over this array.A query can be any of the following three types.
  1. Type ADD: u v
  2. Type MUL: u v
  3. Type REP: u v
  4. Type MAX: l r
  5. Type MIN: l r


HackerEarth Distinct Digits II problem solution


HackerEarth Distinct Digits II problem solution.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define MAX 100001
#define MOD 1000000007
int bit[11][MAX];
vector<ll> arr;
vector<int> C;
int n;
inline void update(int idx,int val,int count){
 while(idx<=n){
  bit[count][idx]+=val;
  idx+=(idx&(-idx));
 }
}
inline int sum(int idx,int count){
 int summ=0;
 while(idx>0){
  summ+=bit[count][idx];
  idx-=(idx&(-idx));
 }
 return summ;
}
inline int query(int l,int r,int count){
 return sum(r,count)-sum(l-1,count);
}
inline int distinct_digits(ll temp){
  bool bit[10];
  int count=0;
  memset(bit,0,sizeof(bit));
  while(temp){
    bit[temp%10]=true;
    temp/=10;
  }
  for(int j=0;j<10;j++)
   if(bit[j])
    count++;
  return count;
}
int main(){
 cin>>n;
 int count;
 arr.resize(n+1);
 C.resize(n+1);
 for(int i=1;i<=n;i++){
  cin>>arr[i];
  C[i]=distinct_digits(arr[i]);
  update(i,1,C[i]);
 }
 int q;
 cin>>q;
 string choice;
 int l,r;
 ll val;
 while(q--){
  cin>>choice;
  if(!choice.compare("ADD")){  // add
    cin>>l>>val;
    arr[l]=(val+arr[l])%MOD;
    update(l,-1,C[l]);
    C[l]=distinct_digits(arr[l]);
    update(l,1,C[l]);
  }else if(!choice.compare("REP")){ // replace
    cin>>l>>val;
    arr[l]=(val)%MOD;
    update(l,-1,C[l]);
    C[l]=distinct_digits(arr[l]);
    update(l,1,C[l]);
  }else if(!choice.compare("MUL")){ // count
    cin>>l>>val;
    arr[l]=(val*arr[l])%MOD;
    update(l,-1,C[l]);
    C[l]=distinct_digits(arr[l]);
    update(l,1,C[l]);
  }else if(!choice.compare("MAX")){
    cin>>l>>r;
    int i,T;
    for(i=10;i>=1;i--){
      T=query(l,r,i);
      if(T){
       break;
      }
    }
    cout<<i<<" "<<T<<endl;
  }else{

    cin>>l>>r;
    int i,T;
    for(i=1;i<=10;i++){
      T=query(l,r,i);
      if(T){
       break;
      }
    }
    cout<<i<<" "<<T<<endl;
  }
 }
return 0;
}

Second solution

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define NIL 0
#define INF (1<<28)
#define MAXN 200001
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 5000000007
#define total 500005
#define M 1000000007
typedef long long int int64;
int BIT[12][100005];
int64 arr[100005];
int dis_cou(int64 x){
    int a[10]={0};
    while(x>0){
        a[x%10]++;
        x=x/10;
    }
    int ret=0;
    for(int i=0;i<10;i++){
        if(a[i])
        ret++;
    }
    return ret;
}
void modify(int dig,int idx,int inc){
    while(idx<=100005){
        BIT[dig][idx]+=inc;
        idx+=(idx&(-idx));
    }
}
int query(int dig,int idx){
    int ret=0;
    while(idx){
        ret+=BIT[dig][idx];
        idx-=(idx&(-idx));
    }
    return ret;
}
int main(){
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>arr[i];
        int x=dis_cou(arr[i]);
        modify(x,i,1);
    }
    int ty,q,c,l,r,u;
    string s;
    int64 v;
    cin>>q;
    while(q--){
        cin>>s;
        if(s=="ADD"){
            cin>>u>>v;
            int x=dis_cou(arr[u]);
            arr[u]+=v;
            arr[u]%=M;
            int x1=dis_cou(arr[u]);
            if(x==x1)
            continue;
            modify(x,u,-1);
            modify(x1,u,1);
            continue;
        }
        if(s=="MUL"){
            cin>>u>>v;
            int x=dis_cou(arr[u]);
            arr[u]*=v;
            arr[u]%=M;
            int x1=dis_cou(arr[u]);
            if(x==x1)
            continue;
            modify(x,u,-1);
            modify(x1,u,1);
            continue;
        }
        if(s=="REP"){
            cin>>u>>v;
            int x=dis_cou(arr[u]);
            arr[u]=v;
            arr[u]%=M;
            int x1=dis_cou(arr[u]);
            if(x==x1)
            continue;
            modify(x,u,-1);
            modify(x1,u,1);
            continue;
        }
        if(s=="MAX"){
            cin>>u>>v;
            for(i=9;i>=1;i--){
                int ans=query(i,v)-query(i,u-1);
                if(ans>0){
                    printf("%d %d\n",i,ans);
                    break;
                }
            }
    
        }
        if(s=="MIN"){
            cin>>u>>v;
            for(i=1;i<10;i++){
                int ans=query(i,v)-query(i,u-1);
                if(ans>0){
                    printf("%d %d\n",i,ans);
                    break;
                }
            }
        }
    }
    return 0;
}