FastPrepExtract Cards

Extract Cards

Infosys logoInfosys● HardOA

Problem statement

You are given some numbered cards which are a permutation of length n, you have to extract each card in increasing order i.e. 1,2,...n. You are allowed to do 3 types of operations any number of times.

  • Take the first card and put it after the last element, doing this will add the number on the first card to your score.
  • Take the last card and put it before the first position, doing this will add the number on the last card to your score.
  • Discard the card if it's in the correct order (1,2,...n), for free.

We want to minimize the final score and print it. Also, the answer can be huge so print the score modulo 1e9+7.

Function

extractCards(cards: int[]) → int

Examples

Example 1

cards = [3, 5, 1, 4, 2]return = 15

First, we move the last 3 cards numbered 2, 4, 1 using the 2nd operation adding 7 to our score. Then we get the new array as [1,4,2,3,5], now we use the 3rd operation to remove the 1st card, so the new array becomes [4,2,3,5], next we use the 1st operation and shift card number 4 at the last adding 4 to our score, so the new array after this operation [2,3,5,4] and our score is 11.

Next, we remove the card numbered 2 using the 3rd operation, so our new array becomes [3,5,4], and we add 0 to our score. Next, we remove card numbered 3 and add 0 to our score. The new array [5,4], now we apply the 2nd operation to shift card number 4 to the first position and add 4 to our score. New score = 15, now we remove the cards numbered 4 & 5 using the 3rd operation and adding 0 to our score both times. So the final score = 15.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ Arr[i] ≤ n

More Infosys problems

See Infosys hiring insights
Saved
public int extractCards(int[] cards) {
    // write your code here
}
cards[3, 5, 1, 4, 2]
expected15
Checking account…