Ross goes for Shopping
All submissions for this problem are available.The Big Billion day has arrived and Ross has $N$ items in his mind which he wants to purchase. After purchasing Ross found that he has total of $M$ type items from 1 to $M$. Now to distinguish the items from each other he wants to arrange them in such a way that items of same type occur continuously. For this he can select any $K$ ( $0$ <= $K$ <= $N$ ) number of items and permute them. The other $N-K$ elements remain untouched. Can you help him to find the minimum value of $K$ for which this is possible? ###Input: - The first line of the input contains two space separated integer $N$ and $M$ - The second line contains N space-separated integers which denotes the type of items he has bought as $A_1$, $A_2$, . . . . . $A_N$ . ###Output: Print a single line containing one integer — minimum value of $K$ for which items of same type occurs continuously. ###Constraints - $1 \leq N \leq 100000$ - $1 \leq M \leq 20$ - $1 \leq A_i \leq M$ ###Sample Input: 6 3 1 2 3 1 2 3 ###Sample Output: 3 ###EXPLANATION: One of the possible way is to select the items at indexes $1st$ , $3rd$ and $5th$. We can permute the selected items by placing the $1st$ ,$3rd$ and $5th$ items at $3rd$ ,$5th$ and $1st$ places respectively to finally get 2 2 1 1 3 3.
|Tags||aditya10_, aditya10_, bitmasking, medium, pelt2019|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.