In this question we will execute the given query on the array elements. The query contains a loop of left rotation, right rotation, and update of array elements.
The logical part of solving the problem is array rotation. A simple way to rotate an array to the left is to replace each element with the next element and the last element with the first element.
We can use the deque data structure to rotate the array efficiently.
Problem Statement - We are given an arr[] array containing integer values. Additionally, we are given a requests[] array containing K queries. We need to execute each query given in requests[] on arr[] array elements according to the following rules.
{0} - Performs a circular left rotation on an array.
{1) - Perform a circular right rotation on the array.
{2, p, q} - Updates the element at index p with q.
{3, p} - Prints the element at index p.
Example
enter
arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};
Output
13,223
Explanation- Let’s execute each query.
{1} -> After rotating the array to the right, the array becomes {51, 8, 9, 13, 44, 76, 67, 21}
{0} -> After rotating the updated array to the left, the array becomes equal to {8, 9, 13, 44, 76, 67, 21, 51}.
< /里>{2, 4, 50} -> After updating the element at index 4 to 50, the array becomes {8, 9, 13, 44, 50, 67, 21, 51}
< /里>{3, 2} -> It prints the element at the second index.
{2, 2, 223}−> Update the element at the second index to 223, and the array becomes {8, 9, 223, 44, 50, 67, 21, 51}. p>
{3, 2} -> It prints the element at the second index.
enter
arr[] = {3, 2, 1}, {{3, 2}, {3, 0}}
Output
1,3
Description - It prints the array from 2nd and 0th index.
enter
arr[] = {76,20,51,78}, queries={{1},{1},{3, 1}}
Output
78
Explanation- After rotating the array to the right 2 times, the array becomes [51, 78, 76, 20]. The element at the first index is 78.
In this approach we will loop through each query and perform operations based on the given query. We replace each element in the array with the next element to rotate it to the left, and each element with the previous element to rotate it to the right.
Step 1- Start looping through each query.
Step 2− If query[p][0] is equal to 0, please follow the steps below.
Step 2.1- Initialize the "temp" variable using the first element of the array.
Step 2.2- Start traversing the array and replace each element with the next element.
Step 2.3- Replace the last element with the "temp" value.
Step 3− If query[p][0] is equal to 1, follow the steps below.
Step 3.1- Store the last element of the array in the "temp" variable.
Step 3.2- Start traversing the array and replace each element with the previous element.
Step 3.3- Update the first element with the "temp" value.
Step 4 - If requests[p][0] is 2, update the array element at the given index with the given value.
Step 5 - If requests[p][0] is 3, print the array value at the given index.
#include <bits/stdc++.h> using namespace std; void performQueries(int arr[], int N, vector<vector<int>> &queries) { int len = queries.size(); for (int p = 0; p < len; p++) { // For left shift if (queries[p][0] == 0) { // left shift array int temp = arr[0]; for (int p = 0; p < N - 1; p++){ arr[p] = arr[p + 1]; } arr[N - 1] = temp; } // For the right shift else if (queries[p][0] == 1) { // Right shift array int temp = arr[N - 1]; for (int p = N - 1; p > 0; p--){ arr[p] = arr[p - 1]; } arr[0] = temp; } // For updating the value else if (queries[p][0] == 2) { arr[queries[p][1]] = queries[p][2]; } // For printing the value else { cout << arr[queries[p][1]] << " "; } } } int main() { int arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; int N = sizeof(arr) / sizeof(arr[0]); vector<vector<int>> queries; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}}; performQueries(arr, N, queries); return 0; }
13 223
Time complexity - O(N*K), traverse the query and rotate the array.
Space complexity - O(1), because we use constant space.
In this method, we will use a deque to store the array elements. Afterwards, to rotate the array to the left, we can pop the previous element from the queue and push it to the end of the queue. Likewise, we can rotate the array in the right direction.
Step 1 - Define the deque and push all array elements into the queue.
Step 2- Use a for loop to iterate through each query.
Step 3- To rotate the array to the left, remove the first element from the beginning of the queue and push it to the end of the queue.
Step 4 - To rotate the array in the correct direction, remove an element from the end of the queue and push that element to the beginning.
Step 5- Update the element or print the element value based on the given query.
#include <bits/stdc++.h> using namespace std; void performQueries(int arr[], int N, vector<vector<int>> &queries) { // Queue to insert array elements deque<int> que; // Add elements to queue for (int p = 0; p < N; p++) { que.push_back(arr[p]); } // total queries int len = queries.size(); for (int p = 0; p < len; p++) { // For left shift if (queries[p][0] == 0) { // Get the first element int temp = que[0]; // Remove the first element que.pop_front(); // Push element at the last que.push_back(temp); } // For the right shift else if (queries[p][0] == 1) { // Get the last element int temp = que[N - 1]; // remove the last element que.pop_back(); // Insert element at the start que.push_front(temp); } // For updating the value else if (queries[p][0] == 2) { que[queries[p][1]] = queries[p][2]; } // For printing the value else { cout << que[queries[p][1]] << " "; } } } int main() { int arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; int N = sizeof(arr) / sizeof(arr[0]); vector<vector<int>> queries; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}}; performQueries(arr, N, queries); return 0; }
13 223
Time complexity - O(N K) for inserting array elements into the queue.
Space Complexity - O(N) for storing elements into a deque.
The deque data structure allows us to perform left and right rotation operations in O(1) time. Therefore, it improves the efficiency of the code that executes a given query.
The above is the detailed content of Reorder and update array elements according to a given query. For more information, please follow other related articles on the PHP Chinese website!