In this HackerEarth Distinct Digits I problem solution Andi and Bob are best friends. They both are good programmers as well. They love programming together because if one of them gets stuck on some problem other can help. But these days Andi is quite busy as his exams are approaching. So, Bob has to tackle the problems alone. While practicing on HackerEarth Bob encounters an interesting problem which he was unable to solve efficiently. So, he asked Andi for help.
The problem as stated by Bob :
Given an array of N elements, Q queries need to be processed over this array. A query can be of any of the following three types:
- Type 0: u v
- Type 1: u v
- Type 2: l r c
HackerEarth Distinct Digits I 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
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;
int choice,l,r;
ll val;
while(q--){
cin>>choice;
if(choice==0){ // add
cin>>l>>val;
arr[l]=val+arr[l];
update(l,-1,C[l]);
C[l]=distinct_digits(arr[l]);
update(l,1,C[l]);
}else if(choice==1){ // replace
cin>>l>>val;
arr[l]=val;
update(l,-1,C[l]);
C[l]=distinct_digits(arr[l]);
update(l,1,C[l]);
}else{ // count
cin>>l>>r>>count;
cout<<query(l,r,count)<<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 a[1000000];
/*
inline void fast(int &x) {
register int64 c = getchar_unlocked();
x = 0;
int64 neg = 0;
for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());
if(c=='-') {
neg = 1;
c = getchar_unlocked();
}
for(; c>47 && c<58 ; c = getchar_unlocked()) {
x = (x<<1) + (x<<3) + c - 48;
}
if(neg)
x = -x;
}*/
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;
int64 v;
cin>>q;
while(q--){
cin>>ty;
if(ty==0){
cin>>u>>v;
int x=dis_cou(arr[u]);
arr[u]+=v;
int x1=dis_cou(arr[u]);
if(x==x1)
continue;
modify(x,u,-1);
modify(x1,u,1);
continue;
}
if(ty==1){
cin>>u>>v;
int x=dis_cou(arr[u]);
arr[u]=v;
int x1=dis_cou(arr[u]);
if(x==x1)
continue;
modify(x,u,-1);
modify(x1,u,1);
continue;
}
else{
cin>>l>>r>>c;
cout<<query(c,r)-query(c,l-1)<<endl;
continue;
}
}
return 0;
}