hack

Hack.java

//Given a number, in the form of an array a[] containing digits from 1 to 9(inclusive). The task is to find the next smallest palindrome larger than this number.
//
//Input :
//The first line is number of test cases T. Every testcase contains two lines. The first line contains the size of the array, second line contains the digits of the number separated by space.
//
//Output:
//In each separate line print the digits of palindrome with spaces in between.
//
//Constraints:
//1<=T<=100
//1<=n<=1000
//1<=a[i]<=9
//
//Example:
//Input:
//1
//11
//9 4 1 8 7 9 7 8 3 2 2
//
//Output:
//9 4 1 8 8 0 8 8 1 4 9

package workspace;

import java.util.Scanner;

public class HAck2 {

	private static Scanner in;

	public static void main(String ar[]) throws Exception {

		in = new Scanner(System.in);
		int n = in.nextInt();
		int a[];
		for (int i = 0; i < n; i++) {
			int length = in.nextInt();
			a = new int[length];
			for (int j = 0; j < length; j++) {
				a[j] = in.nextInt();
			}
			start(a, length);
		}
//		int[] aa =new int[] {2,4,8,8,8,4,3,3,3,8,4,2,8,2,7,4,6,6,5,6,7,3,2,3,5,8,4,2,4,6,5,2,8,3,7,2,3,2,6,8,2,2,2,4,7,6,6,8,4,4,7,2,3,2,5,4,2,8,2,7,2,7,5,3,3,2,2,4,5,2,8,7,8,2,3,2,7,8,7,8,5,2,2,3,5,6,5,5,5,6,3,6,4,7,8,8,7,6,5,7,2,6,5,8,2,6,5,7,8,4,4,5,6,5,8,4,5,4,2,8,6,7,8,4,6,8,3,2,7,7,5,5,3,3,7,3,3,8,4,8,4,3,7,5,3,6,6,7,7,3,2,5,5,5,6,3,8,5,6,8,2,3,4,2,2,3,2,3,3,8,3,6,7,6,5,8,5,7,7,8,8,3,8,3,5,4,5,7,6,3,6,4,6,3,4,4,8,8,4,2,8,3,2,6,3,5,7,8,7,2,5,5,6,2,2,8,6,7,3,4,7,6,6,6,3,3,2,5,2,4,3,3,2,8,8,6,6,3,2,5,6,4,6,4,4,4,3,4,4,3,6,2,4,7,7,3,5,2,4,8,2,4,2,8,7,5,6,4,5,6,2,2,2,7,3,3,8,2,7,6,4,8,6,4,3,8,5,3,2,5,3,5,2,6,3,2,4,3,2,8,5,4,6,3,6,7,2,7,7,3,3,8,3,4,6,3,6,8,8,7,5,3,7,4,3,2,2,2,3,6,6,3,5,3,5,8,5,3,4,5,3,5,3,7,6,7,2,7,2,6,5,3,4,2,5,2,3,6,5,8,2,3,7,4,8,4,2,8,7,7,7,8,3,2,3,7,6,7,7,4,5,7,2,2,2,8,8,3,6,4,3,4,3,8,2,3,6,8,4,8,8,2,7,2,7,3,2,3,7,4,6,8,4,3,3,4,5,4,4,8,6,8,5,6,2,3,6,5,8,8,6,8,3,6,7,3,4,6,6,5,7,8,2,5,6,2,2,2,6,6,3,7,7,5,3,8,8,3,3,4,2,3,8,8,7,3,3,3,3,8,3,7,5,6,2,2,2,6,2,4,4,2,8,3,5,7,5,5,6,5,7,3,8,5,2,7,5,8,4,3,6,3,4,2,3,7,5,5,7,6,3,3,6,2,5,2,2,8,7,3,7,6,6,3,2,8,2,2,5,5,2,6,7,8,5,8,3,7,4,7,2,6,5,3,4,5,8,4,7,6,5,8,2,6,2,7,7,5,6,7,6,8,8,4,2,6,5,7,4,5,8,6,2,8,6,3,2,5,4,4,3,3,3,6,7,4,4,6,3,2,8,7,8,5,4,8,8,3,4,3,3,6,2,4,8,4,3,6,8,5,3,8,5,6,6,6,4,6,2,8,5,7,7,8,5,3,7,7,4,7,8,8,3,3,6,6,2,3,8,8,8,6,4,6,6,4,8,7,8,6,2,8,5,2,8,4,5,4,2,7,2,6,3,2,4,3,2,6,8,4,5,8,5,2,4,8,7,7,5,5,2,2,8,6,4,4,2,6,3,3,6,6,5,2,2,3,8,5,3,6,7,4,4,7,3,5,2,3,2,2,3,6,3,8,5,7,6,3,4,8,6,5,2,6,3,6,6,3,3,4,5,8,3,6,4,5,4,8,4,6,3,6,8,5,7,3,3,4,5,7,6,8,2,3,5,4,3,8,3,5,2,5,5,4,6,7,8,2,4,8,6,8,8,8,4,7,3,3,2,5,6,8,5,7,3,4,4,7,4,4,7,7,7,8,5,4,3,2,6,7,5,4,4,6,5,2,7,7};
//		
//		start(aa,aa.length);

	}

	private static void start(int[] arr, int length) {
		boolean iseven = false;
		boolean incremented = true;
		int mid = length / 2;
		if (arr.length == 1) {
			System.out.println();
			System.out.println(arr[0]);
			return;
		}
		if (arr.length == 2) {
			if (arr[0] < arr[1]) {
				arr[0] = arr[1];
			} else {
				arr[1] = arr[0];
			}
			System.out.println(arr[0] + " " + arr[1]);
			return;
		}
		if (length % 2 == 0) {
			iseven = true;
			if (arr[mid - 1] < arr[mid]) {
				arr[mid - 1] = arr[mid - 1] + 1;
				arr[mid] = 0;
			} else {
				incremented = false;
			}
		} else {
			if (arr[mid - 1] < arr[mid + 1]) {
				if (arr[mid] == 9) {
					arr[mid] = 0;
					arr[mid - 1] += 1;
				} else {
					arr[mid] += 1;
				}
			} else {
				incremented = false;
			}
		}
		if (iseven) {
			for (int i = mid - 1, j = mid; i >= 0 && j <= length - 1; i--, j++) {
				if (incremented && arr[i] >= arr[j]) {
					arr[j] = arr[i];
				} else {
					incrementArray(arr, mid);
				}
			}

		} else {
			for (int i = mid - 1, j = mid + 1; i >= 0 && j <= length - 1; i--, j++) {
				if (incremented && arr[i] >= arr[j]) {
					arr[j] = arr[i];
				} else {
					incrementArray(arr, mid);
				}
			}
		}

		StringBuilder builder = new StringBuilder();
		for (int value : arr) {
			builder.append(value + " ");
		}

		System.out.println(new String(builder).trim());

	}

	private static int[] incrementArray(int[] arr, int pos) {
		if (pos == 0) {
			if (arr[pos] == 9) {
				arr[pos] = 0;
				return getnewArray(arr);
			} else {
				arr[pos] = arr[pos] + 1;
				return arr;
			}
		} else {
			if (arr[pos] == 9) {
				arr[pos] = 0;
				return incrementArray(arr, pos - 1);
			} else {
				arr[pos] = arr[pos] + 1;
				return arr;
			}
		}

	}

	private static int[] getnewArray(int[] arr) {
		int[] newArray = new int[arr.length + 1];
		newArray[0] = 1;
		System.arraycopy(arr, 0, newArray, 1, arr.length);
		return newArray;

	}

}