Code for calculating the books dispatched

Question

Recently I came across this, here is an excerpt from it,

This is another problem about Indraneel's library. His library has one long shelf. His books are numbered and he identifies the books by their number. Each book has a distinct number.

He has lost many books, since many of his friends borrow his books and never bother to return them. He does not want to lose any more books and has decided to keep a record of all books that he lends to his friends. To make the task of borrowing a book a little difficult, he has given the following instructions to his friends: when they borrow a book, they must record in a register its position from the left among the books currently on the shelf.

Suppose there are 5 books in the library and they are arranged as follows:

26 1 42 15 3

If someone walks in and borrows the book 42, then he will record 3 in the register because this book is the third from the left on the shelf. Now the shelf looks like this:

26 1 15 3

If the next person borrow the book 3, he writes down 4 in the register since this is currently the fourth book from the left on the shelf, and so on.

Indraneel knows the initial arrangement of the books in his library at the time that he introduced the register system. After a while he examines his register and would like to know which books have been borrowed. Your task is to write a program to help Indraneel solve this problem.

My approach is count from left if the value of the book is -1 then skip the the book , when the count is equal to the count of the book then print the name of the book and make that value -1.But this approach though correct is giving time limit exceeded on a handful of testcases. Anyone having a better approach for this problem?

Here is the code:

#include <iostream>
#include <vector>

int main(){
    //Input for the number books with the values
    int m;
    std::cin >> m;
    std::vector<int>books(m);

    for(int i=0;i<m;i++){
        std::cin>>books[i];
    }
    //Input for the dispatches made
    int n;
    std::cin >> n;
    std::vector<int>taken(n);

    for(int i=0;i<n;i++){
        std::cin >> taken[i];
    }

    for(int i=0;i<n;i++){
        int bookNum = taken[i]-1;                       //Get the position of book needed
        int k=0;
        for(int j=0;j<m;j++){                          //Go through the book array
            if(books[j] != -1){
                if(k == bookNum){
                    std::cout << books[j] << std::endl; //Display the name if the k is equal
                    books[j] = -1;
                    break;
                }
                k++;                                    //Increment k if the value of the book is not negative
            }
        }
    }

    return 0;
}

Here are the testcases.

Answer 1

Time complexity

Your current solution works, but takes \$O(n*m)\$ time, where \$n\$ is the number of books taken and \$m\$ is the number of total books. This is because for each book taken, you walk the array of books trying to find the right book, skipping over any books previously taken. Given the constraints of: 1 ≤ M ≤ 1000000 and 1 ≤ N ≤ 4000, your program could run for 4 billion iterations, which could exceed the time limit.

There are two solutions I have in mind that have better time complexity.

Solution #1: \$O(n^2)\$

There is a way to achieve \$O(n^2)\$ time complexity by converting each book index of a modified bookshelf and converting it to the original index of the unmodified bookshelf using the taken vector only.

Suppose i-1 books have already been taken off the shelf, and you examine the next book taken, taken[i]. You can transform taken[i] into the original shelf index by examining all the previously taken books in taken[0..i-1]. The trick is to work backwards through the taken books, and whenever a book was taken at or to the left of the current book, you add one to the index. The code looks like this:

int index = taken[i];
for (int j=i-1; j>=0; j--) {
    if (taken[j] <= index)
        index++;
}
// At this point, index is the original index of the book.
std::cout << books[index] << std::endl;

So the complete solution would be:

#include <iostream>
#include <vector>

int main(){
    //Input for the number books with the values
    int m;
    std::cin >> m;
    std::vector<int>books(m);

    // std::ios_base::sync_with_stdio(false);
    for(int i=0;i<m;i++){
        std::cin>>books[i];
    }
    //Input for the dispatches made
    int n;
    std::cin >> n;
    std::vector<int>taken(n);

    for(int i=0;i<n;i++){
        int index;
        std::cin >> index;
        index--;
        taken[i] = index;
        for (int j=i-1;j >= 0;j--) {
            if (taken[j] <= index)
                index++;
        }
        std::cout << books[index] << std::endl;
    }

    return 0;
}

Solution #2: \$O(n*\log^2{m})\$

There is a completely different solution that achieves \$O(n*\log^2{m})\$ time, which in some cases could be faster than \$O(n^2)\$ time. The solution requires the use of a binary indexed tree. You can think of a binary indexed tree as an array with a special property. The special property is that when you add an amount x to an array entry, it also adds x to all the array entries to the right of that entry as well. For example, if the array starts out empty like this:

0 0 0 0 0

and I add 1 to the third array entry, the new array would look like this:

0 0 1 1 1

Adding an amount to an array entry takes \$O(\log m)\$ time, where \$m\$ is the size of the array.

With this in mind, we create a BIT (binary indexed tree) to represent the offset of each book index to its actual index. The BIT starts out with all zeros, meaning each book is in its correct place:

0 0 0 0 0 // Each book is in the starting spot

Suppose we remove the third book from the shelf. We then add -1 to the third spot in the BIT:

0 0 -1 -1 -1 // Books 3,4,5 are at spots 2,3,4 (although book 3 is gone)

Now suppose we remove the third book from the shelf (which is actually book #4 in the original shelf). We then add -1 to the fourth spot in the BIT (where the original book index was):

0 0 -1 -2 -2 // Book 5 is now at spot 3

As you can see, using the BIT, you can map a book to its current location on the shelf with curIndex = index + BIT_LOOKUP(index). Note that looking up a value in a binary indexed tree also takes \$O(\log m)\$ time.

So now, given a new book index, you need to find the original book index for it. The BIT only gives you the reverse mapping (original -> current, not current -> original). Fortunately, you can binary search the bookshelf to find the correct book, since the books are always sorted by original index. There can be books with duplicate original indexes (due to books being removed). If there are duplicates, only the leftmost book is still on the shelf, and the other duplicates are books that have already been taken.

Here is the code:

#include <iostream>
#include <vector>

static inline int BIT_GET(const std::vector<int> &BIT, int i)
{
    int ret = 0;
    i++;
    while (i > 0) {
        ret += BIT[i-1];
        i -= (i & -i);
    }
    return ret;
}

static inline void BIT_ADD(std::vector<int> &BIT, int i, int val)
{
    int max = BIT.size();
    i++;
    while (i < max)
    {
        BIT[i-1] += val;
        i += (i & -i);
    }
}

int bsearch(const std::vector<int> &BIT, int index)
{
    int low  = 0;
    int high = BIT.size()-1;

    while (low <= high) {
        int mid    = low + ((high-low)>>1);
        int midVal = mid + BIT_GET(BIT, mid);

        if (midVal >= index)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

int main(){
    //Input for the number books with the values
    int m;
    std::cin >> m;
    std::vector<int>books(m);
    std::vector<int>BIT(m+2);

    // std::ios_base::sync_with_stdio(false);
    for(int i=0;i<m;i++){
        std::cin>>books[i];
    }
    //Input for the dispatches made
    int n;
    std::cin >> n;
    std::vector<int>taken(n);

    for(int i=0;i<n;i++){
        int index;
        std::cin >> index;
        index--;
        index = bsearch(BIT, index);
        std::cout << books[index] << std::endl;
        BIT_ADD(BIT, index, -1);
    }

    return 0;
}

Answer 2

There are some minor nits about the general code

1. Separate operators like >> with spaces, that makes the code much easier to read. Also you should separate language constructs like for or while with a space afterwards, to readily separate them from function calls.

2. You should use range based loops when you already have the vector fully initialized, it is much more concise.

   int numBooks;
   std::cin >> numBooks;
   std::vector<int> books(numBooks);
   for (auto &book : books){
       std::cin >> book;
   }
   

3. The return 0; at the end is not necessary anymore with modern compilers.

4. You should prefer pre increment ++book over post increment book++, as the later involves a copy (at least for non trivial data types)

5. Actually your code itself is way to complicated. Rather than assigning a new vector you can just shrink the old one

   int numTaken;
   std::cin >> numTaken;
   for (int book = 0; book < numTaken; ++book) {
       int bookId;
       std::cin >> bookId;
       std::cout << books[bookId];
       books.erase(bookId);
   }
   

Full code

#include <iostream>
#include <vector>   

int main() {
    std::ios_base::sync_with_stdio(false);
    size_t numBooks;
    std::cin >> numBooks;
    std::vector<int> books;
    books.reserve(numBooks);
    for (size_t book = 0; book < numBooks; ++book) {
        size_t bookId;
        std::cin >> bookId;
        books.push_back(bookId);
    }

    size_t numBorrowed;
    std::cin >> numBorrowed;
    for (size_t borrow = 0; borrow < numBorrowed; ++borrow) {
        size_t bookId;
        std::cin >> bookId;
        std::cout << books[bookId] << "\n";
        books.erase(bookId);
    }
}