**Problem Description**

There are **N** students labelled from **1** to **N** standing in a queue (initial state of the queue is **1, 2, 3 .... N**).

Also each student has certain number of coins with themselves which they can use to bribe the students standing in front of them to exchange position.

For example: if N = 6 and student 5 bribes student 4 then the queue will look like this: **1, 2, 3, 5, 4, 6**.

You are given an array **A** of size **N** which denotes the current state of the queue, you need to find the **minimum number of bribes** that took place to get the queue into its current state or is it impossible to reach.

**NOTE:**

1 <= N <= 10^{5}

1 <= A[i] <= N

0 <= coins with each student <= 100

First argument is an integer array **A** of size **N** denoting the current state of queue.

Second argument is an integer array **B** of size **N** denoting the coins associated with each student.

**NOTE:**

Return the **minimum number of bribes** which took place to get to the current state of queue from the initial state, else if it is not possible to reach the current state then return **-1**.

Input 1:

A = [2, 1, 5, 3, 4] B = [2, 2, 2, 2, 2]

Input 2:

A = [2, 5, 1, 3, 4] B = [1, 2, 3, 2, 1]

Output 1:

3

Output 2:

-1

Explanation 1:

The initial state => 1 2 3 4 5 After student 5 moves one position ahead by bribing student 4 => 1 2 3 5 4 Now student 5 moves another position ahead by bribing student 3 => 1 2 5 3 4 And student 2 moves one position ahead by bribing student 1 => 2 1 5 3 4 So the final state is 2,1,5,3,4 after three bribing operations.

Explanation 2:

Student 5 can't bribe this many people as it contains only 1 coin.

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

- Hint 1
- Solution Approach
- Complete Solution

Loading...

Start Test