How to add, multiply n numbers to a given range in array and also reverse the range in the array in O(n) time?

Suppose we have an a array L[]={4,1,2,6}. What we need to do is to take a string S consisting of characters A,R,M as input and apply the following algorithm:

for i from 1 to N do 

    if ith letter of S is 'R'
        reverse L[i...N]
    else if ith letter of S is 'A'
        add A to all numbers of L[i..N].
    else if ith letter of S is 'M'
        multiply B to all numbers of L[i..N].

    for all number in L[i..N], module them by C.
print L[i]

end

How to optimize this algorithm so that it runs in O(n) time? Length of the array as well as the string is n. Anyway, any optimization (like removing the loop for add and multiply only ) in this algorithm will be welcomed.

Answer

This answer is quite long, but imho I’ve written it in a rather accessible manner with quite a bit of explanation, so do bear with me for a moment.

It is possible to solve this in O(N) time, assuming that A and B are both integers. Otherwise you can stop reading at this point. But I think there is a need to break apart the algorithm into several distinct steps, each of which is O(N). So it will still be O(N) overall.

Probably the most difficult part of the problem is to figure out how to make this step run in linear time:

    if ith letter of S is 'R'
        reverse L[i...N]

If we just keep staring at the original algorithm, we will be convinced that even if the other steps can be achieved in linear time, this step can never be done in linear time. But that is not true. How do we do it? The way I thought of is to borrow an idea from the double ended queue / deque data structure. Since we know how long the array L is, we just maintain 3 variables, leftmost, rightmost and isReversed.

  • leftmost will hold the current leftmost unused index of the L array, so leftmost is initialized to 1, since we are using one indexed arrays as stated in your question (the term ‘unused’ will be explained later).
  • rightmost will hold the current rightmost unused index of the L array, and hence initialized to N, the length of L.
  • isReversed is used to indicate whether the array is being reversed. This is initialized to false.

Our first task at hand is to figure out the final order of the original elements of array L after all the reverse operations have been applied. We do not need to reverse the array even once to achieve the same effect as reversing. This can be done by traversing the input string S once, and figuring out which element of array L should be at each position after all the reverse operations. For simplicity, we create a new integer array L' that will hold the final original elements of L after applying all the reverse operations, and attempt to fill in L'.

Suppose we are at index i, and S[i] == 'R', so we set isReversed = true to indicate that we are reversing subarray [i..N]. When isReversed == true, we know that the subarray [i..N] is being reversed, so the element at L'[i] should the rightmost unused element, whose index is rightmost. Hence we set L'[i] = L[rightmost], and decrement rightmost by 1 (rightmost = rightmost - 1). Conversely, if isReversed == false we are not reversing subarray [i..N], so the element at L'[i] should be the leftmost unused element, whose index is leftmost. Hence we set L'[i] = L[leftmost], and increment leftmost by 1 (leftmost = leftmost - 1). Subsequent reverse will negate the value of isReversed.

So the current algorithm looks like this in C++ (I assume you’re ok with C++ since one of your question’s tags is C++):

// set up new array L'
int Lprime[N+1];
int leftmost = 1;
int rightmost = N;
bool isReversed = false;

for (int i = 1; i <= N; i++) {
    if (S[i] == 'R') {
        // negate isReversed
        isReversed = !isReversed;
    }

    if (isReversed) {
        Lprime[i] = L[rightmost];
        rightmost = rightmost - 1;
    } else {
        Lprime[i] = L[leftmost];
        leftmost = leftmost + 1;
    }
}

Do verify that this is correct, although I believe it to be so.

Now we look at the rest of the original algorithm:

    else if ith letter of S is 'A'
        add A to all numbers of L[i..N].
    else if ith letter of S is 'M'
        multiply B to all numbers of L[i..N].

    for all number in L[i..N], module them by C.

The hard part seems to be the need to perform a modulo by C on subarray [i..N] for each index i. But based on my limited understanding, this is modulo arithmetic, and we do not really need to perform it on subarray [i..N] for each i. But do not take my word for it. My understanding of number theory is very rudimentary.

Not only that, the steps for the adding and multiplication can be simplified as well. The trick here is to maintain 2 extra variables, let’s call them multiplicativeFactor and additiveConstant. multiplicativeFactor is used to hold a constant we need to multiply to L'[i]. This is initially 1. The additiveConstant variable, as its name suggests, is used to store any constant we need to add to L'[i] after the multiplication of L'[i] by multiplicativeFactor is done. additiveConstant is initailized to 0.

To see this in a more concrete way, let’s set A = 3, B = 5. And suppose S is the string "AMMAAM". Which means the following (NOTE: we ignore the modulo C for now):

  • At index 1, set L'[1] = L'[1] + 3;
  • At index 2, set L'[2] = (L'[2] + 3) * 5;
  • At index 3, set L'[3] = ((L'[3] + 3) * 5) * 5;
  • At index 4, set L'[4] = (((L'[4] + 3) * 5) * 5) + 3;
  • At index 5, set L'[5] = ((((L'[5] + 3) * 5) * 5) + 3) + 3
  • At index 6, set L'[6] = (((((L'[6] + 3) * 5) * 5) + 3) + 3) * 5

Observe that the effect of prior characters 'A' and 'M' “carry over” (or cascade) into the future elements of L'. Let’s express these operations slightly differently:

  • L'[1] = L'[1] + 3
  • L'[2] = 5 * L'[2] + (3 * 5)
  • L'[3] = 5 * 5 * L'[3] + (3 * 5 * 5)
  • L'[4] = 5 * 5 * L'[4] + (3 * 5 * 5 + 3)
  • L'[5] = 5 * 5 * L'[5] + (3 * 5 * 5 + 3 + 3)
  • L'[6] = 5 * 5 * 5 * L'[6] + (3 * 5 * 5 + 3 + 3) * 5

We start to see some patterns.

  • The multiplicative factor of L'[i] is always a power of B. Adding of A has no effect whatsoever on this multiplicative factor. The multiplicative factor is stored in the multiplicativeConstant variable we described above
  • Each time we need to multiply L'[i] by an additional B, there is a need to multiply all the constants (incurred from adding A) by B to obtain the final constant to add to L'[i]. This is the purpose of the additiveConstant variable described above.
  • Multiplication of L'[i] should be done before addition of the additiveConstant to L'[i]

Hence, the final value of each L'[i] can be expressed as multiplicativeConstant * L'[i] + additiveConstant;, and the second main portion of the algorithm looks like this:

int multiplicativeConstant = 1;
int additiveConstant = 0;
for (int i = 1; i <= N; i++) {
    if (S[i] == 'A') {
        additiveConstant += A;
    } else if (S[i] == 'M') {
        multiplicativeConstant *= B;
        // need to multiply all the constants by B as well
        additiveConstant *= B;
    }
    Lprime[i] = multiplicativeConstant * Lprime[i] + additiveConstant;
}

There is one caveat that I’ve not talked about. Integer overflow of multiplicativeConstant and additiveConstant, along with intermediate calculations. If L is an int array, we are in luck, since we can use long long for everything and avoid the overflow. Otherwise, we have to be careful that intermediate computations do not overflow.

Now what about the modulo C operations? In actual fact, they are there to keep every value in L'[i] within the range [0..C-1]. Based on my limited understanding of number theory, we can perform modulo arithmetic like this to achieve the same effect:

int multiplicativeConstant = 1;
int additiveConstant = 0;
for (int i = 1; i <= N; i++) {
    if (S[i] == 'A') {
        additiveConstant = (additiveConstant + (A % C)) % C;
    } else if (S[i] == 'M') {
        multiplicativeConstant = (multiplicativeConstant * (B % C)) % C;
        // need to multiply all the constants by B as well
        additiveConstant = (additiveConstant * (B % C)) % C;
    }
    Lprime[i] = ((multiplicativeConstant * (Lprime[i] % C)) % C + additiveConstant) % C;
}

This addresses the overflow issue of the multiplicativeConstant and additiveConstant variables (but does not prevent overflow of intermediate computations and other variables), and completes our algorithm. I believe this is correct, but do verify it for yourself. I am unable to explain the modular arithmetic stuff since I only know how to use it, so you will have to look it up by yourself. On a side note, the A % C and B % C parts can be done once with their results stored in variables.

Finally, putting everything together:

// set up new array L'
int Lprime[N+1];
int leftmost = 1;
int rightmost = N;
bool isReversed = false;

for (int i = 1; i <= N; i++) {
    if (S[i] == 'R') {
        // negate isReversed
        isReversed = !isReversed;
    }

    if (isReversed) {
        Lprime[i] = L[rightmost];
        rightmost = rightmost - 1;
    } else {
        Lprime[i] = L[leftmost];
        leftmost = leftmost - 1;
    }
}

int multiplicativeConstant = 1;
int additiveConstant = 0;
// factor out A % C and B % C
int aModC = A % C;
int bModC = B % C;
for (int i = 1; i <= N; i++) {
    if (S[i] == 'A') {
        additiveConstant = (additiveConstant + aModC) % C;
    } else if (S[i] == 'M') {
        multiplicativeConstant = (multiplicativeConstant * bModC) % C;
        // need to multiply all the constants by B as well
        additiveConstant = (additiveConstant * bModC) % C;
    }
    Lprime[i] = ((multiplicativeConstant * (Lprime[i] % C)) % C + additiveConstant) % C;
}
// print Lprime

This runs in O(N) time overall.

Once again, if you are worried about integer overflow, assuming that L is an int array, you can use long long for all the variables involved in computation, and you should be fine.

Leave a Reply

Your email address will not be published. Required fields are marked *