# HackerEarth Zeros and Ones problem solution

In this HackerEarth zero and One's problem solution, You are given an array A which contains initially only ones. You can perform two operations:
1. I: Given an index I, update the value of AI to zero.
2. K: Given the value K, print the index of Kth one in the array A. If there is no such index then print 1.

## HackerEarth Zeros and One's problem solution.

`#include <iostream>using namespace std;int tree[4000000];void build(int node, int st, int en) {    if (st == en) {        tree[node] = 1;        return;    }    int mid = (st+en)/2;    build(2*node, st, mid);    build(2*node+1, mid+1, en);    tree[node] = tree[2*node] + tree[2*node+1];}void update(int node, int st, int en, int index) {    if (st == index && en == index) {        tree[node] = 0;        return;    }    int mid = (st+en)/2;    if(index >= st && index <= mid) {        update(2*node, st, mid, index);    } else {        update(2*node+1, mid+1, en, index);    }    tree[node] = tree[2*node] + tree[2*node+1];}int query(int node, int st, int en, int k, int n) {    if (st < 1 || en > n || tree[node] < k) {        return -1;    }    if (st == en && k == 1) {        return st;    }    int val = tree[node];    int mid = (st+en)/2;    int leftNode = tree[2*node];    int rightNode = tree[2*node+1];    if (k >leftNode) {        return query(2*node+1, mid+1, en, k-leftNode, n);    } else {        return query(2*node, st, mid, k, n);    }}int main() {    int N, K, Q, type, I;    cin >> N;    build(1, 1, N);    cin >> Q;    while(Q--) {        cin >> type;        if (type) {            cin >> K;            cout << query(1, 1, N, K, N) << endl;        } else {            cin >> I;            update(1, 1, N, I);        }    }    return 0;}`

### Second solution

`#pragma GCC optimize("O3")#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define pb push_back#define mp make_pair#define fi first#define se second#define be begin()#define en end()#define all(x) (x).begin(),(x).end()#define alli(a, n, k) (a+k),(a+n+k)#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)#define y0 sdkfaslhagaklsldk#define y1 aasdfasdfasdf#define yn askfhwqriuperikldjk#define j1 assdgsdgasghsf#define tm sdfjahlfasfh#define lr asgasgash#define norm asdfasdgasdgsd#define have adsgagshdshfhds#define eps 1e-6#define pi 3.141592653589793using namespace std;template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }typedef vector<int> VII;typedef vector<ll> VLL;typedef pair<int, int> PII;typedef pair<ll, ll> PLL;typedef pair<int, PII > PPII;typedef vector< PII > VPII;typedef vector< PPII > VPPI;const int MOD = 1e9 + 7;const int INF = 1e9;// Template Endconst int MAX = 1e6 + 5;int tree[MAX], n;bool A[MAX];int read(int idx) {    int sum = 0;    while (idx > 0) {        sum += tree[idx];        idx -= (idx & -idx);    }    return sum;}void update(int idx, int val) {    while (idx <= n) {        tree[idx] += val;        idx += (idx & -idx);    }}int binary(int k) {    int l, r, mid, y;    l = 1, r = n;    while (l < r) {        mid = (l + r) >> 1;        y = read(mid);        if (y == k) r = mid;        else if (y < k) l = mid + 1;        else r = mid-1;    }    if (read(l) == k) return l;    else return -1;}int main(int argc, char* argv[]) {    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);    if(argc == 3) freopen(argv[2], "w", stdout);    ios::sync_with_stdio(false);    int q, x, y;    cin >> n >> q;    assert(1 <= n and n <= 1000000);    assert(1 <= q and q <= 1000000);    REP(i, 1, n+1, 1) update(i, 1);    REP(i, 0, q, 1) {        cin >> x >> y;        assert(0 <= x and x <= 1);        assert(1 <= y and y <= n);        if (x == 0) {            if (A[y] == false) update(y, -1);            A[y] = true;        }        else {            cout << binary(y) << endl;        }    }    return 0;}`