Skip to content

Instantly share code, notes, and snippets.

@nakshay
Last active February 9, 2020 11:43
Show Gist options
  • Save nakshay/edc584f5628a60399a6c8bf498f47c39 to your computer and use it in GitHub Desktop.
Save nakshay/edc584f5628a60399a6c8bf498f47c39 to your computer and use it in GitHub Desktop.
hack
//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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment