JavaScript program for range sum query that rotates array counterclockwise by K index

Counterclockwise rotation of an array means rotating all elements of the given array to the left by the given number of indices. In this article, we will implement a JavaScript program for a range sum query that rotates an array counterclockwise by k indices.

Problem Introduction

In this problem, we are given an array containing some integers and another array containing values ​​in the form of pairs. Each pair will be the number of rotations required for the current query, after the given number of rotations we will get a range and have to answer the sum of the elements present in that given range. For example,

Example 1

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [3, 1, 4]
Output 14

illustrate

The number of rotations is 3, so the array after rotating 3 times is 4 5 6 1 2 3.

The elements in the range 1 to 4 are 5, 6, 1 and 2. Therefore, the total is 14.

Example 2

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [8, 0, 3]
Output 18

illustrate

The number of rotations is 8, so the array after 8 rotations is equal to 8 % (array length) rotations, because after the length of the array rotations, the same array appears again meaning 8 rotations is equivalent to 2 Rotate.

Therefore, the array after rotating 8 times is 3 4 5 6 1 2.

In this range, 0 to 3 elements are 3, 4, 5 and 6 respectively. Therefore, the sum is 18.

Naive method

In the simple approach, we will simply perform all the steps described in querying the array. Like, it is given to rotate the array and then we rotate the array elements a given number of times and then check the sum of the elements in the range. Let's see its code -

Example

// function to answer the queries 
function getSum(arr, rotations, L, R){
   var len = arr.length 
   var rot = rotations % len;
   var temp = new Array(len);
   
   // rotating the given array
   for(var i =0;  i< len - rot; i++ ){
      temp[i] = arr[i + rot];
   }
   
   // getting the last elements 
   for(var i = 0; i < rot; i++)    {
      temp[len-rot+i] = arr[i];
   }
   
   // getting the required sum
   var sum = 0;
   for(var i = L; i<=R; i++){
      sum += temp[i];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// defining the queries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]]
 
// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(arr, queries[i][0], queries[i][1], queries[i][2]);
}

Time and space complexity

The time complexity of the above code is O(Q*N), where Q is the number of queries and N is the array size.

The time complexity of the above code is O(N) because we are creating a new array of size N.

Prefix sum method

In the prefix sum method, we will create a prefix sum array, and each index of the prefix sum array contains the sum of all elements up to the current index. Let's see its code -

Example

// function to answer the queries 
function getSum(preSum, rotations, L, R){
   var len = preSum.length 
   var rot = rotations % len;
   
   // updating L and R 
   L = (L + rot) %len
   R = (R + rot) %len
   var sum = 0;
   if(L <= R) {
      if(L == 0) {
         sum = preSum[R];
      }
      else{
         sum = preSum[R]-preSum[L-1];
      }
   }
   else{
      sum += preSum[R];
      sum += preSum[len-1]-preSum[L-1];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]
var preSum = new Array(arr.length)
preSum[0] = arr[0]
for(var i = 1; i<arr.length; i++){
   preSum[i] = preSum[i-1] + arr[i]
}

// defining the quries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]] 

// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(preSum, queries[i][0], queries[i][1], queries[i][2]);
}

Time and space complexity

The time complexity of the above code is O(Q), where Q is the number of queries.

The time complexity of the above code is O(N) because we are creating a new array to store the prefix sum of the array elements.

in conclusion

In this tutorial, we implemented a JavaScript program for a range sum query that rotates an array counterclockwise by k index. Array counterclockwise rotation means rotating all elements of the given array to the left by the given number of indices. We first implemented two methods, a naive method with a time complexity of O(Q*N) and a prefix sum method with a time complexity of O(Q).

The above is the detailed content of JavaScript program for range sum query that rotates array counterclockwise by K index. For more information, please follow other related articles on the PHP Chinese website!