CARDS - Editorial

editorial
#1

PROBLEM LINK:

CARDS

Setter: chayan_d
Tester: debrc

DIFFICULTY:

Easy - medium

PREREQUISITES:

Arrays and arithmetic operations

PROBLEM:

You have a deck of N-cards and each card has a number scribbled on it.

You are given an array A of length N having distinct integers. A_0 represent the number on bottom-most card and A_{N-1} represent the number on top-most card.

There is a number in the array that has the lowest value and a number that has the highest value. Your goal is to remove both the cards which have these numbers.

A removal of card is defined as either removing an element from the top of deck or removing from the bottom of the deck of cards.

Print the minimum number of removals it would take to remove both the minimum and maximum element from the deck of card.

EXPLANATION:

There are 3 possible cases:

  1. Delete both min and max element from left.
  2. Delete both from right
  3. Delete one from left and other from right.

Steps :

  • We will store index of min and max element in i and j variable (where j always points to the greater index).
  • For case 1: no of elements to be deleted = j+1
  • For case 2: no of elements to be deleted = n - i
  • For case 3: no of elements to be deleted = (i+1) + (n-j)
  • Return min of above 3 cases

TIME COMPLEXITY:

The time complexity is O(N)

SOLUTIONS:


#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int nums[n];

    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    int i = 0, j = 0;

    //find min and max position
    for (int k = 0; k < n; k++)
    {
        if (nums[i] < nums[k])
            i = k;
        if (nums[j] > nums[k])
            j = k;
    }

    //to make sure j points to greater index
    if (i > j){
        swap(i, j);
    }

    int case1 = (j + 1);         // if both of them are removed from left side of array
    int case2 = (n - i);         // if both of them are removed from right side of array
    int case3 = (i + 1 + n - j); // if one elemnt is removed from left and one from right
    
    cout<< min(case3, min(case2, case1));
}

Feel free to share your approach.

Suggestions are welcomed as always had been.

1 Like