Palin (Java) time limit exceeded

Discussion on all problems hosted at SPOJ

Palin (Java) time limit exceeded

Postby thunderchicken » Sat Nov 25, 2006 03:30

So, I realized the error of my ways in trying to attempt a recursive solution. I have an iterative solution that essentially tries to use the first half to make the second half a palindrome > k. However, I'm still exceeding the time limit. Looking at the code below, I suspect the problem has to do with my use of Strings. Would using a char array representation be faster, and if so, is there a way to quickly compare char arrays as needed?

Code: Select all
public static void main (String[] args) throws java.lang.Exception {
      java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));

      int nTestCases = Integer.parseInt(r.readLine());
      
      for (int i = 0; i < nTestCases; i++) {
         String strNum = r.readLine();
         System.out.println(getNextPalin(strNum));
      }
   }
   
   public static String getNextPalin(String num) {
      int halfIndex = (int) Math.ceil(num.length() / 2.0);
      String firstHalf = num.substring(0, halfIndex);
      String secondHalf = num.substring(halfIndex);
      String palin = generatePalin(num, firstHalf, secondHalf);

      if (palin.compareTo(num) == 1) {
         return palin;
      }
      
      firstHalf = incrementString(firstHalf);
      return generatePalin(firstHalf + secondHalf, firstHalf, secondHalf);
   }
   
   private static String generatePalin(String num, String firstHalf, String secondHalf) {
      int length = num.length();
      if (length == 1) {
         if (num.equals("9")) {
            return "11";
         }
         return incrementString(num);
      }
      
      int halfIndex = (int) Math.ceil(length / 2.0);
      StringBuilder newStr = new StringBuilder();
      newStr.append(firstHalf);
      
      int startIndex = (length % 2 == 0) ? (firstHalf.length()-1) : (firstHalf.length()-2);
      
      for (int i = startIndex; i >= 0; i--) {
         newStr.append(firstHalf.charAt(i));
      }
      
      return newStr.toString();
   }
   
   public static String incrementString(String toIncrement) {
      StringBuilder incrementedStr = new StringBuilder();
   
      int len = toIncrement.length();
      
      boolean carry = true;
      for (int i = len-1; i >=0; i--) {
         char ch = toIncrement.charAt(i);
         char newCh = ch;
         if (carry) {
            newCh = increment(ch);
            carry = false;
            if (newCh == '0') {
               carry = true;
            }
         }   
         incrementedStr.insert(0, newCh);
      }
      if (carry) {
         incrementedStr.insert(0, '1');
      }
      
      return incrementedStr.toString();
   }
   
   private static char increment(char ch) {
      if (ch == '0') return '1';
      if (ch == '1') return '2';
      if (ch == '2') return '3';
      if (ch == '3') return '4';
      if (ch == '4') return '5';
      if (ch == '5') return '6';
      if (ch == '6') return '7';
      if (ch == '7') return '8';
      if (ch == '8') return '9';
      else return '0';
   }
thunderchicken
 
Posts: 2
Joined: Fri Nov 24, 2006 07:28

Postby vinaye » Sat Nov 25, 2006 11:01

Why did you start a new thread if there already exists one for this problem? As for the problem, your algorithm seems to be fine in that you have to generate the next palindrome from the first half of the string. Its easy if you handle the number as an array of integers.
You may wonder what happens to earth when everyone could compete!
vinaye
 
Posts: 154
Joined: Fri Jul 28, 2006 21:26
Location: India


Return to ProblemSet Archive

Who is online

Users browsing this forum: No registered users and 1 guest