Valuable Time

Last Updated on March 23, 2022 by Ria Pathak

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.

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
using namespace std;
// Function to rotate the sequence according to given rule.
void rotate(queue &q1){
    int a = q1.front();
    q1.pop();
    q1.push(a);
}
int main(){
    int n, element;
    int time = 0;
    cin>>n;
    queue q1;
    queue 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<


						 

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 dq1 = new LinkedList();
       Deque dq2 = new LinkedList();
        for(int i=0;i

						 

def rotate(q1):

	a = q1[0]
	q1.pop(0)
	q1.append(a)

time = 0
n = int(input())
q1 = list(map(int,input().split()))
q2 = list(map(int,input().split()))

while len(q1) and len(q2):

	if q1[0] == q2[0]:

		q1.pop(0)
		q2.pop(0)
		time += 1

	else:

		rotate(q1)
		time += 1

print(time)

[forminator_quiz id="2322"]

This article tried to discuss the concept of Queues. Hope this blog helps you understand and solve the problem. To practice more problems on Queues you can check out MYCODE | Competitive Programming.