# HackerEarth Retrieve passwords problem solution

In this HackerEarth Retrieve passwords problem solution A password is a number that is exactly divisible by 9. It is the largest number that can be formed by rearranging all the available digits in a provided range (L, R) inclusive and adding another number of your own choice to this sequence at any position. The password is missing a digit that must be added. You are also given an encrypted number. You are also provided q queries. The queries could be of two types.

Update a digit at a position.
Determine the largest number that is divisible by 9 in the provided range with the mentioned conditions. In the provided mentioned number, print its xth digit.
`#include <bits/stdc++.h>#//include <ext/pb_ds/assoc_container.hpp>#//include <ext/pb_ds/tree_policy.hpp>#//include <ext/pb_ds/detail/standard_policies.hpp>//using namespace __gnu_pbds;using namespace std;//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;//insert(), find_by_order(), order_of_key()typedef long long int ll;typedef unsigned long long int llu;#define pb push_back#define eb emplace_back#define mp make_pair#define vi vector<int>#define vl vector<ll>#define vvi vector<vi>#define ref(i, n) for (int i = 0; i < n; ++i)#define rer(i, n) for (int i = n; i >= 0; --i)#define refv(i, n, k) for (int i = k; i <= n; ++i)#define rerv(i, n, k) for (int i = k; i >= n; --i)#define fi first#define pii pair<int, int>#define piii pair<pii, int>#define priority_queue_2 priority_queue<int, vector<int>, greater<int>>#define se second#define fast1 ios_base::sync_with_stdio(false)#define fast2 cin.tie(NULL)inline void pin(int n){    printf("%d\n", n);}#define onec(x) __builtin_popcount(x);#define all(x) x.begin(), x.end()double PI = acos(-1);const int inf = 0x3f3f3f3f;#define sv()         \    int t;           \    scanf("%d", &t); \    while (t--)#define MOD 1000000007#define TRACE#ifdef TRACE#define trace1(x) cerr << #x << ": " << x << endl;#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;#else#define trace1(x)#define trace2(x, y)#define trace3(x, y, z)#define trace4(a, b, c, d)#define trace5(a, b, c, d, e)#define trace6(a, b, c, d, e, f)#endifstruct node{    vector<int> p;    node()    {        p.resize(10, 0);    }};string s;int n;vector<node> v(1000005);void update(int pos, int val, int no){    while (pos <= n)    {        v[pos].p[no] += val;        pos += pos & (-pos);    }}int sum(int pos, int no){    int s = 0;    while (pos > 0)    {        s += v[pos].p[no];        pos -= pos & (-pos);    }    return s;}int main(){    bool ti= false;    fast1;    fast2;    cin >> s;    n = s.size();    clock_t start, end;    start = clock();    assert(n <= 1000000);    for (int i = 0; i < n; i++)        update(i + 1, 1, s[i] - '0');    int q;    cin >> q;    assert(q <= 500000);    vector<int> m(10, 0);    while (q--)    {        int t;        cin >> t;        assert(t == 2 || t == 1);        if (t == 1)        {            int x, y;            cin >> x >> y;            assert(x>0 && x <= n);            assert(y >= 0 && y < 10);            int old = s[x-1] - '0';            if(old==y)                 continue;            s[x-1] = (char)(y + '0');            update(x , -1, old);            update(x , 1, y);            //cout<< s << endl;        }        else        {            int l, r, x;            cin >> l >> r >> x;            assert(l <= n && r >= l && r <= n && l>0);            assert(x>0 && x <= (r - l + 2));            for (int i = 0; i < 10; i++)            {                m[i] = sum(r, i);                m[i] -= sum(l-1, i);                //trace2(i,m[i]);            }            int ss = 0;            for (int i = 1; i < 10; i++)            {                ss += ((i % 9) * (m[i] % 9)) % 9;                ss %= 9;            }            m[9 - ss]++;            for (int i = 9; i >= 0; i--)            {                if (m[i] >= x)                {                    cout << i << endl;                    break;                }                x -= m[i];            }        }    }    end = clock();    if(ti){    double time_taken = double(end - start) / double(CLOCKS_PER_SEC);    cout << "Time taken by program is : " << fixed         << time_taken << setprecision(5);    cout << " sec " << endl;}    return 0;}`