Pseudo Sorting From Array

Viewed 646

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).

Constraints:

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

My Solution:

#include <stdio.h>

int main()
{
    int T, N, ara[100000], count, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i++)
    {
        scanf("%d", &N);
        for (j = 0; j < N; j++)
        {
             scanf("%d", &ara[j]);
        }
        count = 0;
        for (j = 1; j < N; j++)
        {
            if (ara[j] < ara[j - 1])
            {
                count++;
            }
        }
        if (count <= 1)
        {
            printf("YES\n");
        }
        else if (count > 1)
        {
            printf("NO\n");
        }
    }
    return 0;
}

But, I am getting error in some test cases though my code is working well for the given test cases. Can anyone help me to identify the bug(s)?

enter image description here

3 Answers

If you have n numbers in ara, then the algorithm would look like this

#include <stdio.h>

int main() {
    int failCount = 0, i = 1, n = 3;
    int ara[3] = {3, 2, 1};
    int prevMax = ara[0] - 1;
    while ((failCount < 2) && (i < n)) {
        if (ara[i - 1] > ara[i]) {
            failCount++;
        }
        if (failCount < 2) {
            if ((i > 1) && (prevMax > ara[i])) failCount++;
            if (prevMax < ara[i - 1]) prevMax = ara[i - 1];
        }
        i++;
    }
    printf("%d", failCount);
    return 0;
}

I'm aware that you do not want to read all of it, so you need to read the numbers during the loop rather than read all of them before the loop, the code above was a simplified code to illustrate the logic.

Also, you need to consider examples such as

3 1 2

where 3 > 1 and that increases the counter, but later you compare 1 < 2 and it looks to be correct, yet, 3 was greater than 2 as well. This is what my second if is solving.

Sample tests

2 0 1

enter image description here

Your test counts the number of cases where 2 adjacent numbers are out of order. This is not sufficient for the problem. Here is a counter-example:

1
3
3 1 2

3 1 2 produces a count of 1 but requires 2 swaps.

Once you detect an element that is out of order, you must test if swapping it with the previous element fixes the problem:

#include <stdio.h>

int main() {
    int T = 0, ara[100000], count, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i++) {
        int N = 0;
        scanf("%d", &N);
        for (j = 0; j < N; j++) {
            ara[j] = 0;
            scanf("%d", &ara[j]);
        }
        count = 0;
        for (j = 1; j < N && count < 2; j++) {
            if (ara[j] < ara[j - 1]) {
                int temp = ara[j - 1];
                ara[j - 1] = ara[j];
                ara[j] = temp;
                count++;
                if (j > 1) {
                    j -= 2;
                }
            }
        }
        if (count <= 1) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

You could get rid of the array and avoid converting the remaining numbers once a failure has been identified:

#include <stdio.h>

int main() {
    int T = 0, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i++) {
        int N = 0, n1 = 0, n2 = 0, n3, count = 0, c, temp;
        scanf("%d", &N);
        if (N >= 2) {
            scanf("%d%d", &n1, &n2);
            if (n1 > n2) {
                temp = n1;
                n1 = n2;
                n2 = temp;
                count++;
            }
            for (j = 2; j < N; j++) {
                n3 = 0;
                scanf("%d", &n3);
                if (n2 > n3) {
                    count++;
                    if (count > 1)
                        break;
                    if (n1 > n3) {
                        count++;
                        break;
                    }
                    n1 = n3;
                } else {
                    n1 = n2;
                    n2 = n3;
                }
            }
        }
        /* read and discard the rest of the line */
        while ((c = getchar()) != EOF && c != '\n')
            continue;
        if (count <= 1) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

There is no way to avoid scanning the whole array to make sure that there is no more than one inversion. If we find an inversion, we also need to check if a swap will restore non-decreasingness. I guess that the code below does a minimum of comparisons.

int i;

// Detect the first inversion, if any (b is always a[i-1])
b= a[0];
if (b > ara[1]) {
    i= 1;
}
else {
  b= a[1];
  for (i= 2; i < n; b= ara[i], i++) {
    if (b > ara[i]) {
      // If b = a[i-1] will cause a non-decreasing sequence, fail
      if (ara[i-2] > ara[i])
        return false;
      else
        // The swap might fix the inversion
        i++;
        break;
    }
  }
}

// Detect the second inversion, if any
for ( ; i < n; b= ara[i], i++) {
  if (b > ara[i]) {
      // There is a second inversion, fail
      return false;
  }
}

return true;

There is a subtlety: when a first inversion is found, we check if ara[i-2] <= ara[i], but not ara[i-1] <= ara[i+1]. In fact, we leave this second test to the detection of a second inversion, with b still ara[i-1] and continuing from ara[i+1].

We also handled the first two elements differently, to avoid ara[i-2] being undefined.

Related