[Solution] Pseudo Sorted Array solution codechef

Pseudo Sorted Array solution codechef – An array AA of length NN is said to be pseudo-sorted if it can be made non-decreasing after performing the following operation at most once.

[Solution] Pseudo Sorted Array solution codechef

  • Choose an ii such that 1iN11≤i≤N−1 and swap AiAi and Ai+1Ai+1

Given an array AA, determine if it is pseudo-sorted or not.

Input Format

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN – the size of the array AA.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the array AA.

Output Format

For each testcase, output YES if the array AA is pseudo-sorted, NO otherwise.

You may print each character of YES and NO in uppercase or lowercase (for example, yesyEsYes will be considered identical).

[Solution] Pseudo Sorted Array solution codechef

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases do not exceed 21052⋅105

Sample Input 1 

3
5
3 5 7 8 9
4
1 3 2 3
3
3 2 1

Sample Output 1 

YES
YES
NO

Pseudo Sorted Array solution Explanation

Test case 1: The array is already sorted in non-decreasing order.

Test case 2: We can choose i=2i=2 and swap A2A2 and A3A3. The resulting array will be [1,2,3,3][1,2,3,3], which is sorted in non-decreasing order.

Test case 3: It can be proven that the array cannot be sorted in non-decreasing order in at most one operation.

For Solution

Click here

Leave a Comment