Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Distinct Digits I problem solution

YASH PAL, 31 July 2024
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:
  1. Type 0: u v
  2. Type 1: u v
  3. Type 2: l r c
HackerEarth Distinct Digits I problem solution

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;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes