Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerRank Library Query problem solution

YASH PAL, 31 July 2024

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.

HackerRank Library Query problem solution

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("%dn", 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();
}

coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes