Queries to search for an element in an array and modify the array based on given conditions

0 0 7 minutes read

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 array
void 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 operations
void operations(vector<int> &queries,
                vector<int> &arr)
{
    for(auto x : queries)
        doOperation(arr, x);
}
 
// Driver Code
int 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 approach
 
import 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 array
def 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 
# operations
def operations(queries, arr):
 
    for x in queries:
        doOperation(arr, x)
 
# Driver Code
if __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 approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that perform the given
// queries for the given array
static 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 []arr
static void print(List<int> arr)
{
     
    // Traverse the array []arr
    foreach(int x in arr) 
    {
 
        // Print element
        Console.Write(x + " ");
    }
}
 
// Function to perform operations
static void operations(int []queries,
                       List<int> arr)
{
    foreach(int x in 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
    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 array
function 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 Code
let arr = [ 1, 2, 3, 4 ];
let x = 3;
 
// Given queries
let queries = [ 12, 2, 13 ];
 
// Perform queries
operations(queries, arr);
 
// Print the resultant array
print(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 zambiatek!