Krdytkyu

Question

We are given an array (indexed from 1) of N elements on which we make M queries:

add(Left, Right, X) - all the elements between the position Left and Right (1<=Left<=Right<=N) are raising their values with X.

After all the operations are completed, print the array.

example

Array: 1 1 1 4 5 6

operations: (1, 5, 2), (2, 3, 10)

Final array: 3 13 13 6 7 6

Discussion

I managed to produce the expected output but I was wondering if this code can be simplified using a queue data structure somehow?

The complexity of this code is M*N (please correct me if I am wrong) - This naive approach is looping all the operations for every element of the input array.

Naive approach

#include <iostream>



using namespace std;



int Queue[1000], backInd;



void push(int i)

{

    ++backInd;

    Queue[backInd] = i;

}



void applyOperations(int input, int operations, int N, int M)

{

    for (int x = 0; x < N; ++x){

        int item = input[x];

        int offset = 0;

        for (int op = 0; op < M; ++op)

        {

            if (x + 1 >= operations[op + offset] && x + 1 <= operations[op + offset + 1])

            {

                item += operations[op + offset + 2];

            }

            offset += 2;

        }

        push(item);

    }

}



int main()

{

    backInd = -1;

    frontInd = 0;

    int input = {1, 1, 1, 4, 5, 6};

    int operations = {1, 5, 2, 2, 3, 10};

    int N = 6;

    int M = 2;



    applyOperations(input, operations, N, M);



    for (int x = 0; x < N; ++x) {

        cout << Queue[x] << " ";

    }



    return 0;

}

I'm not really sure if your code matches the intention of the task, albeit you possibly might get the expected results.

At first, you are producing a new array, whereas the task is 'all elements raise their values', which I read that you should modify the array in place.

Then I'd rather assume that you should implement a single operation in a function which then gets called M times, example:

void applyOperation(int array, size_t length, size_t begin, size_t end, int operator);



int array = { 1, 1, 1, 4, 5, 6 };

applyOperation (array, sizeof(array)/sizeof(*array), 1, 5, 2);

applyOperation (array, sizeof(array)/sizeof(*array), 2, 3, 10);

// print result

M is 2, function is called twice (I renamed N to length...).

Whether you now implement the function to execute one operation at a time or all at once, you shouldn't iterate over the entire array and then check if the index is in the range, instead you'd iterate over the range directly:

void applyOperation(int array, size_t length, size_t begin, size_t end, int operator)

{

    --begin; --end; // they want one-based indices? bad idea for C++,

                    // but OK, then let's adjust them to zero-based...



    for(;; begin != end; ++begin)

    {

         array[begin] += operator;

    }

}

Looks much easier, doesn't it? What's actually lacking yet is checking the range of begin and end, assuming you manage this yourself...

Now if you want to have all operations in one single go, then it is much more comprehensive if you iterate over the operations in first place:

void applyOperations(int input, int operations, int N, int M)

{

    for(int i = 0; i < M; ++i, operations += 3)

    // this assumes: each operation occupies three subsequent values

    {

         // now using operations[0] as begin, operations[1] as end

         // and operations[2] as operator just like above



         // it might be unacceptable to modify the operations array, then you'd

         // need a separate loop variable compared to above; but IF it is,

         // then you should keep the operations const anyway:

         //int const operations

    }

}

Finally: You tagged the question C++ – your code could as well be good old C, though. In C++, you'd rather use std::array or std::vector than raw arrays. Whichever you use, you don't have to provide size/length separately, both come with their own member function size() giving the number of elements (not size in bytes as sizeof operator does, so you'd avoid the ugly sizeof(x)/sizeof(*x) at the same time – even more important: you could provide a bad value for length, this cannot happen with the C++ containers as these manage their length/size on their own).

void applyOperation(std::vector<int> values, size_t begin, size_t end, int operator)

{

    --begin; --end;

    for(;; begin != end; ++begin)

    {

         values[begin] += operator;

    }

}

The loop still looks similar, but range checking would now use values.size() instead of a length parameter.

One final note: Did you notice that I changed the parameter types to size_t? Two reasons for this:

1. 
   size_t is an unsigned type. Negative indices are meaningless in the given task, so why allow them at all?


2. 
   size_t mapped to the native type large enough to hold an object of maximum size on given system (which means at the same time that it will always be large enough to index any member in an array). This is obviously not relevant in given case, as your arrays' sizes most likely won't ever exceed the range of ordinary int - but you simply cannot fail this way, so if you get used to it, you'll be well prepared for the future...

frontInd is never declared. It's only ever assigned to, so that assignment can just be removed.

Avoid using namespace std - that's not a namespace that's designed to be imported wholesale, and you could introduce surprising bugs that way. Given that we have a single use of std::cout and nothing else from the standard library, it's actually costing more code lines/characters (as well as more cognitive overhead) than just writing the prefix where needed.

Inseparable data should be contained in a class. Here, backInd and Queue belong together; no outside code ever needs to use backInd, so it could be a private member. That said, backInd is always equal to x when writing, so we could just index that way.

Consider an alternative algorithm - the current approach will be slow when the number of operations gets large. Consider looping over the operations just once, recording the delta of value at each position (so each operation will update just two values - an increment at the beginning of its range and a corresponding decrement at the end). Then track the cumulative total when writing the output.