In this HackerEarth Shil and Round Numbers problem solution Shil likes Round numbers very much . A number is called Round number if its non-negative and its first and last digits are same. For example 0 , 3 , 343 and 50005 are round numbers whereas 1000 is not a round number.
Shil has an array A1 , A2 .. AN . He wants to answer Q queries of following two type :
  1. l r : Find total number of round numbers in range [l, r]
  2. i K : Update ith element of array A to K i.e perform the operation Ai = K.
  3. Since you are the friend of Shil , he asks for your help.

HackerEarth Shil and Round Numbers problem solution


HackerEarth Shil and Round Numbers problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int bt[200011];
ll A[200011];
int N;
int round(ll x){
if(x<0) return 0;
if(x==0) return 1;
int p=x%10;
int r;
while(x>0){
r=x%10;
x/=10;
}
return ( p==r );
}
void update(int ind,int val){
while(ind<=N){
bt[ind]+=val;
ind+=(ind&-ind);
}
}
int query(int ind){
int ans=0;
while(ind>0){
ans+=bt[ind];
ind-=(ind&-ind);
}
return ans;
}
int main(){
freopen("input-1.txt","r",stdin);
freopen("output-1.txt","w",stdout);


int Q;
cin >> N >> Q;
for(int i=1;i<N+1;i++){
cin >> A[i];
update(i,round(A[i]));
}
ll t,l,r;
while(Q--){
cin >> t >> l >> r;
if(t==2){
update(l,-round(A[l]));
A[l]=r;
update(l,round(A[l]));
}
else{
cout<<query(r)-query(l-1)<<"\n";
}
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define max 200002
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
ll tree[max];

ll read(ll idx)
{
ll sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(ll idx ,ll val)
{
while (idx <= max) {
tree[idx] += val;
idx += (idx & -idx);
}
}
int main()
{
int n,q,i;
ll l,r;
scanf("%d%d",&n,&q);
ll a[n+2];
for(i = 1; i <= n; i++) {
scanf("%Ld",&a[i]);
if(a[i] < 0) {
a[i] = 0;
continue;
}
vector<ll>x;
while(a[i]) {
x.push_back(a[i]%10);
a[i] /= 10;
}
if(x[0] == x[x.size()-1]) {
a[i] = 1LL;
}
if(a[i]) {
update(i,a[i]);
}
}
while(q--) {
scanf("%d%Ld%Ld",&i,&l,&r);
if(i == 1) {
printf("%Ld\n",read(r)-read(l-1));
}
else {
vector<ll>x;
if(r < 0) {
if(a[l]) {
update(l,-1);
a[l] = 0;
}
continue;
}
while(r) {
x.push_back(r%10);
r /= 10;
}
if(x[0] == x[x.size()-1]) {
if(!a[l]) {
update(l,1);
a[l] = 1;
}
}
else {
if(a[l]) {
update(l,-1);
a[l] = 0;
}
}
}
}
return 0;
}