I tried to solve the problem in O(n).
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the minimumBribes function below.
static void minimumBribes(int[] q) {
int total=0;
int bribe;
int n=q.length;
int temp;
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=i+1;
}
for (int i = 0; i < n - 1; i++) {
bribe = 0;
if (q[i] > arr[i]) {
bribe = Math.abs(q[i] - i - 1);
}
// System.out.print(bribe + " ---- " + q[i] + " & " + arr[i] + " --->");
// for (int a : arr) {
// System.out.print(a + " ");
// }
// System.out.print(" --> ");
if (bribe > 2) {
System.out.println("Too chaotic");
return;
} else if (bribe == 2 && i + 2 < n) {
temp = arr[i + 2];
arr[i + 2] = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
} else if (bribe == 1 && i + 1 < n) {
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
total += bribe;
// for (int a : arr) {
// System.out.print(a + " ");
// }
// System.out.println();
}
System.out.println(total);
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
int[] q = new int[n];
String[] qItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int qItem = Integer.parseInt(qItems[i]);
q[i] = qItem;
}
minimumBribes(q);
}
scanner.close();
}
}
I looked onto the editorial. It described the same solution of changing the temporary array. Please help me identify what error I made here.