Given an array arr[] consisting of N integers and an integer X, the task is to print the array after performing X queries denoted by an array operations[]. The task for each query is as follows:
- If the array contains the integer operations[i], reverse the subarray starting from the index at which operations[i] is found, to the end of the array.
- Otherwise, insert operations[i] to the end of the array.
Examples:
Input: arr[] = {1, 2, 3, 4}, X = 3, operations[] = {12, 2, 13}
Output: 1 12 4 3 2
Explanation:
Query 1: arr[] does not contain 12. Therefore, append it to the last. Therefore, arr[] = {1, 2, 3, 4, 12}.
Query 2: arr[] contains 2 at index 1. Therefore, reverse the subarray {arr[1], arr[4]}. Therefore, arr[] = {1, 12, 4, 3, 2}.
Query 3: arr[] does not contain 13. Therefore, append it to the last. Therefore, arr[] = {1, 12, 4, 3, 2, 13}.Input: arr[] = {1, 1, 12, 6}, X = 2, operations[] = {1, 13}
Output: 1 12 4 3 2
Approach: The simplest approach is that for each query search the whole array to check if the concerned integer is present or not. If present at an index i and the current size of the array is N, then reverse the subarray {arr[i], … arr[N – 1]} . Otherwise, insert the searched element at the end of the array. Follow the steps below to solve the problem:
- Create a function to linearly search for the index of an element in an array.
- Now for each query, if the given element is not present in the given array, append that to the end of the array.
- Otherwise, if it is present at any index i, reverse the subarray starting from index i up to the end.
- After completing the above steps, print the resultant array.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to reverse the subarray// over the range [i, r]void rev(vector<int> &arr, int l, int r){ // Iterate over the range [l, r] while (l < r) { int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; }}// Function that perform the given// queries for the given arrayvoid doOperation(vector<int> &arr, int o){ // Search for the element o int ind = -1; // Current size of the array int n = arr.size(); for(int i = 0; i < n; i++) { // If found, break out of loop if (arr[i] == o) { ind = i; break; } } // If not found, append o if (ind == -1) arr.push_back(o); // Otherwise, reverse the // subarray arr[ind] to arr[n - 1] else rev(arr, ind, n - 1);}// Function to print the elements// in the vector arr[]void print(vector<int> &arr){ // Traverse the array arr[] for(int x : arr) { // Print element cout << x << " "; }}// Function to perform operationsvoid operations(vector<int> &queries, vector<int> &arr){ for(auto x : queries) doOperation(arr, x);}// Driver Codeint main(){ // Given array arr[] int arr[] = { 1, 2, 3, 4 }; int x = 3; // Given queries vector<int> queries({ 12, 2, 13 }); // Add elements to the vector vector<int> arr1; for(int z : arr) arr1.push_back(z); // Perform queries operations(queries, arr1); // Print the resultant array print(arr1);}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function that perform the given // queries for the given array static void doOperation( ArrayList<Integer> arr, int o) { // Search for the element o int ind = -1; // Current size of the array int n = arr.size(); for (int i = 0; i < n; i++) { // If found, break out of loop if (arr.get(i) == o) { ind = i; break; } } // If not found, append o if (ind == -1) arr.add(o); // Otherwise, reverse the // subarray arr[ind] to arr[n - 1] else reverse(arr, ind, n - 1); } // Function to reverse the subarray // over the range [i, r] static void reverse( ArrayList<Integer> arr, int l, int r) { // Iterate over the range [l, r] while (l < r) { int tmp = arr.get(l); arr.set(l, arr.get(r)); arr.set(r, tmp); l++; r--; } } // Function to print the elements // in the ArrayList arr[] static void print(ArrayList<Integer> arr) { // Traverse the array arr[] for (int x : arr) { // Print element System.out.print(x + " "); } } // Function to perform operations static void operations( int queries[], ArrayList<Integer> arr) { for (int x : queries) doOperation(arr, x); } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1, 2, 3, 4 }; int x = 3; // Given queries int queries[] = { 12, 2, 13 }; // Add elements to the arraylist ArrayList<Integer> arr1 = new ArrayList<>(); for (int z : arr) arr1.add(z); // Perform queries operations(queries, arr1); // Print the resultant array print(arr1); }} |
Python3
# Python3 program for # the above approach# Function to reverse the # subarray over the range # [i, r]def rev(arr, l, r): # Iterate over the # range [l, r] while (l < r): arr[l], arr[r] = (arr[r], arr[l]) l += 1 r -= 1# Function that perform the given# queries for the given arraydef doOperation(arr, o): # Search for the # element o ind = -1 # Current size of # the array n = len(arr) for i in range(n): # If found, break out # of loop if (arr[i] == o): ind = i break # If not found, append o if (ind == -1): arr.append(o) # Otherwise, reverse the # subarray arr[ind] to # arr[n - 1] else: rev(arr, ind, n - 1)# Function to print the # elements in the vector # arr[]def print_array(arr): # Traverse the # array arr[] for x in arr: # Print element print(x, end = " ")# Function to perform # operationsdef operations(queries, arr): for x in queries: doOperation(arr, x)# Driver Codeif __name__ == "__main__": # Given array arr[] arr = [1, 2, 3, 4] x = 3 # Given queries queries = [12, 2, 13] # Add elements to the vector arr1 = [] for z in arr: arr1.append(z) # Perform queries operations(queries, arr1) # Print the resultant array print_array(arr1)# This code is contributed by Chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function that perform the given// queries for the given arraystatic void doOperation(List<int> arr, int o){ // Search for the element o int ind = -1; // Current size of the array int n = arr.Count; for(int i = 0; i < n; i++) { // If found, break out of loop if (arr[i] == o) { ind = i; break; } } // If not found, append o if (ind == -1) arr.Add(o); // Otherwise, reverse the // subarray arr[ind] to arr[n - 1] else reverse(arr, ind, n - 1);}// Function to reverse the subarray// over the range [i, r]static void reverse(List<int> arr, int l, int r){ // Iterate over the range [l, r] while (l < r) { int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; }}// Function to print the elements// in the List []arrstatic void print(List<int> arr){ // Traverse the array []arr foreach(int x in arr) { // Print element Console.Write(x + " "); }}// Function to perform operationsstatic void operations(int []queries, List<int> arr){ foreach(int x in queries) doOperation(arr, x);}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = { 1, 2, 3, 4 }; //int x = 3; // Given queries int []queries = { 12, 2, 13 }; // Add elements to the arraylist List<int> arr1 = new List<int>(); foreach (int z in arr) arr1.Add(z); // Perform queries operations(queries, arr1); // Print the resultant array print(arr1);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function that perform the given// queries for the given arrayfunction doOperation(arr, o){ // Search for the element o let ind = -1; // Current size of the array let n = arr.length; for(let i = 0; i < n; i++) { // If found, break out of loop if (arr[i] == o) { ind = i; break; } } // If not found, append o if (ind == -1) arr.push(o); // Otherwise, reverse the // subarray arr[ind] to arr[n - 1] else reverse(arr, ind, n - 1);}// Function to reverse the subarray// over the range [i, r]function reverse(arr, l, r){ // Iterate over the range [l, r] while (l < r) { let tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; l++; r--; }}// Function to print the elements// in the ArrayList arr[]function print(arr){ document.write(arr.join(" "));}// Function to perform operations function operations(queries, arr){ for(let x = 0; x < queries.length; x++) doOperation(arr, queries[x]);}// Driver Codelet arr = [ 1, 2, 3, 4 ];let x = 3;// Given querieslet queries = [ 12, 2, 13 ];// Perform queriesoperations(queries, arr);// Print the resultant arrayprint(arr);// This code is contributed by avanitrachhadiya2155</script> |
Output
1 12 4 3 2 13
Time Complexity: O(N*X) where N is the size of the given array and X is the number of queries.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
