Valuable Time

Concepts Used

Queues.

Difficulty Level

Easy.

Problem Statement :

Ravi is asked to solve a challenge by his friend Salma. He is given a sequence and is asked to perform operations on it such that the sequence becomes the same as Salma’s sequence in minimal time, and he need to clear the sequence during the process.

In rotation operation, Ravi can remove the first element of his sequence and push it in the end, it takes 1 unit of time.

In clear operation, an element can be removed from the front, each remove costs 1 unit of time for Ravi’s list. It is not necessary that clearing operation will be performed only after the sequence becomes the same, we can also clear if the front element of both sequences are the same. The clear operation will be performed on both the sequences and for Salma’s sequence it will take zero amount of time.

See original problem statement here

EXAMPLE:

Input
5
5 4 2 3 1
5 2 1 4 3

Output
7

Sample test case explanation
We can clear the first element as it is the same. Remaining sequence of Ravi is [4,2,3,1] and Salma is [2,1,4,3].
Since the first of both lists are different, perform the rotation operation and Ravi's sequence will become [2,3,1,4].
We can clear the first element as it is the same. The remaining sequence of Ravi is 
[3,1,4], and Salma is [1,4,3].
Since the first of both lists are different, perform the rotation operation and Ravi's sequence will become [1,4,3].
We can clear the first element as it is the same. The remaining sequence of Ravi is [4,3] and Salma is [4,3].
We can clear the first element as it is the same. The remaining sequence of Ravi is [3] and Salma is [3].
We can clear the first element as it is the same. The remaining sequence of Ravi is [] and Salma is [].
So a total of 7 units of time is taken.

EXPLANATION:

Push all the elements in their respective queues using data structures in c++.

Now start traversing from the front of each queue.

If the front element of both the queues match, pop them out.

Else rotate.

Also increase the time counter in both the cases.

SOLUTIONS:

#include<bits/stdc++.h>
using namespace std;
// Function to rotate the sequence according to given rule.
void rotate(queue<int> &q1){
    int a = q1.front();
    q1.pop();
    q1.push(a);
}
int main(){
    int n, element;
    int time = 0;
    cin>>n;
    queue<int> q1;
    queue<int> q2;
    for(int i = 0; i < n; i++){
        cin>>element;
        q1.push(element);
    }
    for(int j = 0; j < n; j++){
        cin>>element;
        q2.push(element);
    }
    // Execute the operation till both the queues are not empty.
    while(!q1.empty() && !q2.empty()){
        // If in order then clear the list.
        if(q1.front() == q2.front()){
            q1.pop();
            q2.pop();
            time++;
        }
        // Else rotate the list as per given rule.
        else{
            rotate(q1);
            time++;
        }
    }
    // Output the total time.
    cout<<time<<endl;
    return 0;
}
import java.util.*;
  import java.io.*;
  public class Main {

    public static void main(String args[]) throws IOException {
      Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
       Deque<Integer> dq1 = new LinkedList<Integer>();
       Deque<Integer> dq2 = new LinkedList<Integer>();
        for(int i=0;i<n;i++){
          int x=sc.nextInt();
          dq1.add(x);
        }
        //sc.nextLine();
        for(int i=0;i<n;i++){
          int x=sc.nextInt();
          dq2.add(x);
        }
        int t=0;
   while(!dq1.isEmpty() && !dq2.isEmpty())
   {
      if(dq1.peekFirst()== dq2.peekFirst()){
        dq1.removeFirst();dq2.removeFirst();t++;
      }
      else{
       dq1.addLast(dq1.peekFirst());
       dq1.removeFirst();
       t++;
      }

   }
      System.out.print(t);
    }
  }

SPACE COMPLEXITY-O(N)

Previous post Sum Subarray
Next post Stack Challenge

Leave a Reply

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