Algorithm


Problem Name: Data Structures - Library Query

Problem Link: https://www.hackerrank.com/challenges/heavy-light-2-white-falcon/problem?isFullScreen=true

In this HackerRank in Data Structures - Library Query solutions,

A giant library has just been inaugurated this week. It can be modeled as a sequence of N consecutive shelves with each shelf having some number of books. Now, being the geek that you are, you thought of the following two queries which can be performed on these shelves.

 

  • Change the number of books in one of the shelves.

  • Obtain the number of books on the shelf having the kth rank within the range of shelves.

 

A shelf is said to have the kth rank if its position is k when the shelves are sorted based on the number of the books they contain, in ascending order.

 

Can you write a program to simulate the above queries?

 

Input Format
The first line contains a single integer T, denoting the number of test cases.
The first line of each test case contains an integer N denoting the number of shelves in the library.
The next line contains N space separated integers where the ith integer represents the number of books on the ith shelf where 1<=i<=N.
The next line contains an integer Q denoting the number of queries to be performed. Q lines follow with each line representing a query.
Queries can be of two types:

 

  • 1 x k - Update the number of books in the xth shelf to k (1 <= x <= N).
  • 0 x y k - Find the number of books on the shelf between the shelves x and y (both inclusive) with the kth rank (1 <= x <= y <= N, 1 <= k <= y-x+1).

 

Output Format
For every test case, output the results of the queries in a new line.

 

Constraints
1 <= T <= 5
1 <= N <= 104
1 <= Q <= 104
The number of books on each shelf is always guaranteed to be between 1 and 1000.

 

Sample Input

 

2
2
1 2
2
0 1 2 1
0 1 2 2
4
4 3 2 1
4
0 1 1 1
1 1 1
0 1 1 1
0 1 4 3

 

Sample Output

 

1
2
4
1
2

 

Explanation

 

There are two test cases :

  1. The first test case contains only two shelves which can be represented as [1, 2]. Two queries are to be processed : i) The first query asks for smallest number of books between the 1st and 2nd shevles which is 1. ii) The second query asks for the 2nd smallest number of books between the 1st and 2nd shevles which is 2.
  2. The second test case contains four shelves which can be represented as [4, 3, 2, 1]. Four queries are to be processed :

    i) The first query asks for the smallest number of books in the 1st shelf which is 4.

    ii) The second query updates the number of books in the 1st shelf to 1. Hence the shelves now look like [1, 3, 2, 1].

    iii) The third query asks for the smallest number of books in the 1st shelf which is now 1. iv) The last query asks for the 3rd smallest number of books between the 1st and 4th shelves which is 2.

 

 

 

Code Examples

#1 Code Example with C Programming

Code - 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;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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;
                }
            }
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - 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();
}
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - 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]))
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Heavy Light 2 White Falcon solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Starfleet solution in Hackerrank - Hacerrank solution C, C++, java,js, Python