Hello Everyone, I went by the analysis and used quick sort to sort the sub
lists and then checked if its sorted and returned the error-index. But this is
resulting in Runtime Error.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
public static void main(String[] args) {
FastReader f = new FastReader();
int t = f.nextInt();
int[][] array = new int[t][];
for (int i = 0; i < t; i++) {
int n = f.nextInt();
array[i] = new int[n];
int[] evenArr, oddArr;
oddArr = new int[n / 2];
evenArr = n % 2 == 0 ? new int[n / 2] : new int[(n / 2)
+ 1];
for (int k = 0; k < n; k++) {
if (k % 2 == 0) {
evenArr[k / 2] = f.nextInt();
} else {
oddArr[k / 2] = f.nextInt();
}
}
int result = getResult(n, oddArr, evenArr);
System.out.println("Case #" + (i + 1) + ": " + (result
>= 0 ? result : "OK"));
}
}
private static int getResult(int s, int[] oddArr, int[] evenArr) {
quickSort(evenArr, 0, evenArr.length - 1);
quickSort(oddArr, 0, oddArr.length - 1);
int temp = evenArr[0];
int i = 0;
for (; i < oddArr.length; i++) {
if(temp>evenArr[i]){
return (i*2)-1;
}
if(evenArr[i]>oddArr[i]){
return i*2;
}
temp = oddArr[i];
}
if(s%2!=0){
if(temp>evenArr[i]){
return (i*2)-1;
}
}
return -1;
}
private static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int partitionIndex = getPartition(arr, start, end);
quickSort(arr, start, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, end);
}
}
private static int getPartition(int[] arr, int start, int end) {
int partition = arr[start];
int j = start + 1;
for (int i = start + 1; i <= end; i++) {
if (arr[i] < partition) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j++;
}
}
int temp = arr[start];
arr[start] = arr[j - 1];
arr[j - 1] = temp;
return j - 1;
}
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/6670076f-bc36-41fa-99fc-712a5a7be71a%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
