HackerEarth Zeros and Ones problem solution

31 July 2024 YASH PAL

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:

I: Given an index I, update the value of AI to zero.
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 Ones problem solution

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.141592653589793

using 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 End

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

coding problems