[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 1≤i≤N−11≤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, yes, yEs, Yes will be considered identical).

[Solution] Pseudo Sorted Array solution codechef

• 1≤T≤10001≤T≤1000
• 2≤N≤1052≤N≤105
• 1≤Ai≤1091≤Ai≤109
• Sum of NN over all test cases do not exceed 2⋅1052⋅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“