Pseudo Sorted Array - CodeChef Solution | April Long Challenge 2022

   

Pseudo Sorted Array CodeChef Solution | April Long Challenge 2022

Problem Code: PSEUDOSORT

Problem: An array A of length N is said to be pseudo-sorted if it can be made non-decreasing after performing the following operation at most once.

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

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

Input Format:

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

Output Format:

For each testcase, output YES if the array A 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).

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

Explanation:

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

Test case 2: We can choose i=2 and swap A2 and A3. The resulting array will be [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.

Java Code:

import java.util.*;

import java.io.*;

public class Main {

    public static void main (String[] args) throws IOException {

        Scanner in = new Scanner(System.in);

        int test = in.nextInt();

        while (test-- > 0) {

            int n = in.nextInt();

            int[] arr = new int[n];

            for (int i = 0; i < n; i++)

                arr[i] = in.nextInt();

            

            int swapCount = 0;

            for (int i = 1; i < n; i++) {

                if (arr[i] < arr[i - 1]) {

                    swap(arr, i, i - 1);

                    if (i >= 2 && arr[i - 2] > arr[i - 1])

                        swapCount += 2;

                    else

                        swapCount++;

                }

            } 

            System.out.println(swapCount <= 1 ? "YES" : "NO");

        }

    }

    private static void swap(int[] arr, int i, int j) {

        int tempVal = arr[i];

        arr[i] = arr[j];

        arr[j] = tempVal;

    }

}

I'll be giving you the solution as well as the deep explanation of the approach, for all questions during the live contest, so make sure you have subscribed to our YouTube channel😇. Click here to redirect to out YouTube channel.