HackerRank Library Query problem solution

In this HackerRank Library Query problem solution, we have a giant library that is inaugurated. we need to change the number of books on the shelves in the library. and obtain the number of books on the shelf having kth rank within the range of shelves. we have given the number of shelves in the library. and the number of books present on the shelf. and the number of queries that we need to perform on the given data.

Problem solution in Python programming.

class FenwickTree2D:
    def __init__(self, x,y):
        self.size_x = x
        self.size_y = y
        self.data = [[0]*self.size_y for _ in range(self.size_x)]
 
    def sum(self, x1, y1):
        if min(x1,y1) <= 0: return 0
        s = 0
        x = x1
        while x >= 0:
            y = y1
            while y >= 0:
                s += self.data[x][y]
                y = (y & (y+1)) - 1
            x = (x & (x+1)) - 1
        return s

    def sumrange(self, x1, y1, x2, y2): 
        return self.sum(x2, y2) \
               - self.sum(x1-1, y2) - self.sum(x2, y1-1) \
               + self.sum(x1-1,y1-1)

    def add(self, x1, y1, w):
        assert min(x1,y1) > 0
        x = x1
        while x < self.size_x:
            y = y1
            while y < self.size_y:
                self.data[x][y] += w
                y |= y + 1
            x |= x + 1

for t in range(int(input())):
    N = int(input())
    arr = list(map(int,input().split()))
    t = FenwickTree2D(10001,1001)
    for i in range(len(arr)):
        t.add(i+1,arr[i],1)
    Q = int(input())
    for q in range(Q):
        c = list(map(int,input().split()))
        if c[0]==1:
            t.add(c[1],arr[c[1]-1],-1)
            arr[c[1]-1] = c[2]
            t.add(c[1],arr[c[1]-1],1)
        else:
            def select(l,r,k):
                lo,hi=1,1000
                while lo < hi:
                    med = (hi+lo)//2
                    a = t.sumrange(l,0,r,med)
                    if a>=k:
                        hi = med
                    else:
                        lo = med+1

                if not t.sumrange(l,0,r,lo) >= k:
                    raise ValueError
                return lo
            print(select(c[1],c[2],c[3]))

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {
    
    public static class SumTree {
        private int size;
        private int[] tree;
        
        public SumTree(int n) {
            size = 1;
            while (size <= n) {
                size *= 2;
            }
            tree = new int[size * 2];
        }
        
        public void clear() {
            Arrays.fill(tree, 0);
        }
        
        public void set(int index, int value){
            index += size;
            tree[index] = value;
            while (index > 1) {
                index /= 2;
                tree[index] = tree[index * 2] + tree[index * 2 + 1];
            }
        }
        
        private int getSum(int v, int l, int r, int L, int R) {
            if (l == L && r == R) {
                return tree[v];
            }
            
            if (l > r) {
                return 0;
            }
            
            int middle = (L + R) / 2;
            return getSum(v * 2, l, Math.min(middle, r), L, middle) +
                    getSum(v * 2 + 1, Math.max(middle + 1, l), r, middle + 1, R);
        }
        
        public int getSum(int l, int r) {
            return getSum(1, l, r, 0, size - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        new Solution().run();
    }
    
    StreamTokenizer in;
    PrintWriter out;

    private int nextInt() throws IOException {
       in.nextToken();
       return (int)in.nval;
    }

    private void run() throws IOException {
       in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
       out = new PrintWriter(System.out);
       solve();
       out.flush();
    }
    
    private void solve() throws IOException {
        int t = nextInt();
        for (int i = 0; i < t; i++) {
            doTest();
        }
    }
    
    public Solution() {
        trees = new SumTree[1001];
        for (int i = 0; i < trees.length; i++) {
            trees[i] = new SumTree(10001);
        }
        
        blockTrees = new SumTree[blocks];
        for (int i = 0; i < blockTrees.length; i++) {
            blockTrees[i] = new SumTree(10001);
        }
    }
    
    SumTree[] trees;
    SumTree[] blockTrees;
    int blockSize = 32;
    int blocks = 32;
    
    private void doTest() throws IOException {
        int n = nextInt();
        
        for (int i = 0; i < trees.length; i++) {
            trees[i].clear();
        }
        
        for (int i = 0; i < blockTrees.length; i++) {
            blockTrees[i].clear();
        }
        
        int[] shelves = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            shelves[i] = nextInt();
            trees[shelves[i]].set(i, 1);
            blockTrees[shelves[i] / blockSize].set(i, 1);
        }
        
        int q = nextInt();
        for (int i = 0; i < q; i++) {
            int qType = nextInt();
            if (qType == 1) {
                int shelve = nextInt();
                trees[shelves[shelve]].set(shelve, 0);
                blockTrees[shelves[shelve] / blockSize].set(shelve, 0);
                int k = nextInt();
                shelves[shelve] = k;
                trees[shelves[shelve]].set(shelve, 1);
                blockTrees[shelves[shelve] / blockSize].set(shelve, 1);
            } else {
                int x = nextInt();
                int y = nextInt();
                int k = nextInt();
                int count = 0;
                for (int block = 0; block < blocks; block++) {
                    int blockCnt = blockTrees[block].getSum(x, y);
                    //System.out.println("block = " + Integer.valueOf(block) + ", blockCnt = " + Integer.valueOf(blockCnt) + ", count = " + Integer.valueOf(count));
                    if (count + blockCnt >= k) {
                        for (int shelve = block * blockSize;; shelve++) {
                            count += trees[shelve].getSum(x, y);
                            if (count >= k) {
                                out.println(shelve);
                                break;
                            }
                        }
                        break;
                    }
                    count += blockCnt;
                }
            }
        }
    }
}

Problem solution in C++ programming.

#include <bits/stdc++.h>
#define msg(x) cout << #x << " = " << x << endl
using namespace std;

const int maxN = 10224;
const int maxRoot = 2014;

int a[maxN], t, n, root;
vector<int> bucket[maxRoot];

void update() {
    int idx, val;
    cin >> idx >> val;
    idx--;
    int bidx = idx / root;
    for (int i = 0; i < bucket[bidx].size(); i++) {
        if (bucket[bidx][i] == a[idx]) {
            bucket[bidx][i] = a[idx] = val;
            break;
        }
    }
    sort(bucket[bidx].begin(), bucket[bidx].end());
}

void query() {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    vector<int> tmp;
    tmp.reserve(root + 10);
    int lb = l/root + 1;
    int rb = r/root - 1;
    while (l/root == lb - 1 && l < r) {
        tmp.push_back(a[l]);
        l++;
    }
    while (r >= l && r/root == rb + 1) {
        tmp.push_back(a[r]);
        r--;
    }
    sort(tmp.begin(), tmp.end());
    int lo = 1, hi = 1000; //worst algorithm ever
    while (lo < hi) {
        int mid = lo + hi >> 1;
        int cnt = upper_bound(tmp.begin(), tmp.end(), mid) - tmp.begin();
        for (int i = lb; i <= rb; i++) {
            cnt += upper_bound(bucket[i].begin(), bucket[i].end(), mid) - bucket[i].begin();
        }
        if (cnt >= k) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << hi << "\n";
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        root = sqrt(1.0 * n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i % root == 0) {
                bucket[i / root].clear();
            }
            bucket[i / root].push_back(a[i]);
        }
        for (int i = 0; i < maxRoot; i++) {
            sort(bucket[i].begin(), bucket[i].end());
        }
        int q;
        cin >> q;
        while (q--) {
            int cmd;
            cin >> cmd;
            if (cmd == 1) {
                update();
            } else {
                query();
            }
        }
    }
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    int t;
    scanf("%d", &t);
    
    while (t--) {
        int n;
        scanf("%d", &n);
        int s[n+1];
        
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i]);
        }
        
        int qc;
        scanf("%d", &qc);
        
        while (qc--) {
            int q[4];
            for (int i = 0; i < 3; i++) {
                scanf("%d", &q[i]);
            }
            if (q[0] == 1) {
                s[q[1]] = q[2];
            } else {
                scanf("%d", &q[3]);
                int bc[1001] = {0};
                
                for (int i = q[1]; i <= q[2]; i++) {
                    bc[s[i]]++;
                }
                
                int count = q[3];
                for (int i = 1; i <= 1000; i++) {
                    count -= bc[i];
                    if (count <= 0) {
                        printf("%d\n", i);
                        break;
                    }
                }
            }
        }
    }
    
    return 0;
}

Problem solution in JavaScript programming.

"use strict";

const fs = require("fs");

process.stdin.resume();
process.stdin.setEncoding("utf-8");

let inputString = "";
let currentLine = 0;

process.stdin.on("data", inputStdin => {
    inputString += inputStdin;
});

process.stdin.on("end", _ => {
    inputString = inputString
        .trim()
        .split("\n")
        .map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

const parse10 = s => parseInt(s, 10);

const readInt = () => parse10(readLine());

const readLineAsInts = () =>
    readLine()
        .split(" ")
        .map(parse10);

const counts = new Array(1001);

function solve(n, shelves, queries) {
    const ans = [];
    for (let [t, x, y, z] of queries) {
        --x;
        if (t === 1) {
            shelves[x] = y;
        } else {
            counts.fill(0);
            --y;
            --z;
            for (let i = x; i <= y; ++i) {
                ++counts[shelves[i]];
            }
            let s = 0;
            for (let i = 1; i <= 1000; ++i) {
                if (s <= z && z < s + counts[i]) {
                    ans.push(i);
                    break;
                }
                s += counts[i];
            }
        }
    }
    return ans;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
    let t = readInt();
    while (t--) {
        const n = readInt();
        const shelves = readLineAsInts();
        const q = readInt();
        const queries = new Array(q);
        for (let i = 0; i < q; ++i) {
            queries[i] = readLineAsInts();
        }
        const ans = solve(n, shelves, queries);
        ws.write(ans.join('\n') + '\n');
    }
    ws.end();
}