FastPrep
Problem · Greedy

Extract Cards

Learn this problem
● Hardinfosys logoinfosysOA

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

    drafts saved locally
    public int extractCards(int[] cards) {
    // write your code here
}
    cards[3, 5, 1, 4, 2]
    expected15
    checking account