I have tried all the test cases i could think of. Please help.
this is my code link. i will tell the logic i have used.
i dealt with single digit no. separately as well as all 9s. Then i divided the string in two halves, and compared them. If the first part comes out to be greater than other i reverse it and concatenate it otherwise i increment it and concatenate it.
http://www.codechef.com/viewsolution/4605014
import java.util.Arrays;
public class Main {
static int[] arr = new int[1000002];
static StringBuilder sb = new StringBuilder();
public static void stringToIntArr(String s) {
int len = s.length();
for (int i = 0; i < len; i++) {
arr[i] = Integer.parseInt("" + s.charAt(i));
}
}
public static void palin(String s) {
int len = s.length();
boolean flag9 = true;
int i = 0;
stringToIntArr( s);
if (len <= 1) {
System.out.print(11);
return;
}
if (len == 2) {
int a1 = Integer.parseInt(s);
if (a1 == 99) {
System.out.print(101);
} else if (a1 == 10) {
System.out.print(11);
} else {
for (i = 1; i <= 9; i++) {
if ((11 * i <= a1) && a1 < (11 * (1 + i))) {
System.out.print(11*(i+1));
break;
}
}
}
return;
}
int mid = 0, j;
boolean isodd = true;
if ((len & 1) != 0) {
mid = (len - 1) >> 1;
i = mid - 1;
j = mid + 1;
} else {
isodd = false;
mid = (len - 1) >> 1;
i = mid;
j = mid + 1;
}
for (int k = i, z=j; k>=0;k--,z++) {
if (arr[k] != 9||arr[k]!=arr[z]) {
flag9 = false;
break;
} else
continue;
}
if (flag9 == true) {
len++;
Arrays.fill(arr,0, len, 0);// prints the new number
arr[0] = 1;
arr[len-1] = 1;
System.out.print(printArray(len ));
sb = sb.delete(0, sb.length());
return;
}
// cal the mid ele
while (i >= 0&&j <=len) {
if (arr[i] != arr[j]) {
break;
}
i--;
j++;
}
if (i<0) {// number given is a palindrome just increment the middle
// element
//System.out.println("1");
IncrementAndCreateMirrorLeftPalin(mid, len);
} else {// the string is half matched
//System.out.println("2");
boolean incre=false;
if(arr[i]<arr[j])incre=true;
while (j <= len && i >= 0) {
arr[j] = arr[i];
i--;
j++;
//System.out.println("--");
}
if(incre)IncrementAndCreateMirrorLeftPalin(mid, len);
else
System.out.print(printArray(len));
sb.delete(0, sb.length());
}
}
public static void IncrementAndCreateMirrorLeftPalin(int mid, int len){
//System.out.println("2*");
int i,j;
int carry = 0;
if ((len & 1) != 0) {
i = mid - 1;
j = mid + 1;
arr[mid]++;
if (arr[mid] == 10) {
arr[mid] = 0;
carry = 1;
}
} else {
i = mid;
j = mid + 1;
arr[i]++;
if (arr[i] == 10) {
arr[i] = 0;
carry = 1;
}
arr[j]=arr[i];
}
while (carry != 0) {
arr[i] += carry;
if (arr[i] == 10) {
arr[i] = 0;
arr[j] = arr[i];
carry = 1;
i--;
j++;
} else
carry = 0;
if (i < 0)
break;
}
if (carry == 1)
System.out.print(printArray(carry, len));
else
System.out.print(printArray(len));
sb = sb.delete(0, sb.length());
}
static String printArray(int len) {
// System.out.println("2**");
for (int i = 0; i < len; i++) {
sb.append(arr[i]);
// System.out.println("2*");
}
return sb.toString();
}
static String printArray(int carry, int len) {
sb.append(carry);
for (int i = 0; i < len; i++) {
sb.append(arr[i]);
}
sb.append(carry);
return sb.toString();
}
public static void main(String[] args) throws java.lang.Exception {
try {
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
String s;
s = r.readLine();
int m = Integer.parseInt(s);
while ((s = r.readLine()) != null) {
if(s.isEmpty())break;
m--;
palin(s);
if(m>0)System.out.print("\n");
}
} catch (Exception e) {
System.out.println("ex" + e.toString());
e.printStackTrace();
System.exit(0);
// orsimply
// return;
}
}
}
What is wrong with the output ? What they want, I;m consumed in checking test cases.
Is there any problem of newline? can any one provide me test cases for successful submission?