Watson asks Does Permutation Exist
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Watson gives an array A of N integers A1, A2, ..., AN to Sherlock. He wants Sherlock to reorganize the array in a way such that no two adjacent numbers differ by more than 1.
Formally, if reorganized array is B1, B2, ..., BN, then the condition that | Bi - Bi + 1 | ≤ 1, for all 1 ≤ i < N(where |x| denotes the absolute value of x) should be met.
Sherlock is not sure that a solution exists, so he asks you.
First line contains T, number of test cases. Each test case consists of N in one line followed by N integers in next line denoting A1, A2, ..., AN.
For each test case, output in one line YES or NO denoting if array A can be reorganized in required way or not.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109
- Sum of N over all test cases ≤ 2*105
Input: 2 4 3 2 2 3 2 1 5 Output: YES NO
Test case 1:
No need to reorganise.
Test case 2:
No possible way.
|Tags||cook75, darkshadows, logic, simple, sorting|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.