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;
}