Faster way to find Palindrome. Accepted C++ Solution.
My solution is based on Finding a palindrome number (>=N)first and then I will check it for a prime or not.\nGiven a number N, I will check it for a palindrome,
My solution is based on Finding a palindrome number (`>=N`)first and then I will check it for a prime or not.\nGiven a number `N`, I will check it for a palindrome, if not - then I find the closest palindrome (`>N`)\nTo find the closest palindrome is the hardest part of this program. Here is the whole discussion. The discussion based on "array int" but I implemented the number considering a string.\n\nIf you have any **question** regarding my **code**, please **comment**. I will try to answer.\n\nFor example, if the input number is \u201C2 3 5 4 5\u201D, the output should be \u201C2 3 6 3 2\u201D. And if the input number is \u201C9 9 9\u201D, the output should be \u201C1 0 0 1\u201D.\n\nThere can be three different types of inputs that need to be handled separately.\n\n1) The input number has all 9s. For example \u201C9 9 9\u201D. Output should be \u201C1 0 0 1\u201D i, e., `answer = input+2`\n\n2) For input \u201C1 2 3 4\u201D. Output should be \u201C1 3 3 1\u201D\n\nHow to convert a given number to a greater palindrome? To understand the solution, let us first define the following two terms:\nLeft Side: The left half of given number. Left side of \u201C1 2 3 4 5 6\u201D is \u201C1 2 3\u201D and left side of \u201C1 2 3 4 5\u201D is \u201C1 2\u201D\nRight Side: The right half of given number. Right side of \u201C1 2 3 4 5 6\u201D is \u201C4 5 6\u201D and right side of \u201C1 2 3 4 5\u201D is \u201C4 5\u201D\nTo convert to palindrome, we can either take the mirror of its left side or take mirror of its right side. However, if we take the mirror of the right side, then the palindrome so formed is not guaranteed to be next larger palindrome. So, we must take the mirror of left side and copy it to right side. But there are some cases that must be handled in different ways. See the following steps.\n\nWe will start with two indices i and j. i pointing to the two middle elements (or pointing to two elements around the middle element in case of n being odd). We one by one move i and j away from each other.\n\n\nStep 1. Initially, ignore the part of left side which is same as the corresponding part of right side. For example, if the number is \u201C8 3 4 2 2 4 6 9\u2033, we ignore the middle four elements. i now points to element 3 and j now points to element 6.\n\nStep 2. After step 1, following cases arise:\n\nCase 1: Indices i & j cross the boundary.\nThis case occurs when the input number is palindrome. In this case, we just add 1 to the middle digit (or digits in case n is even) propagate the carry towards MSB digit of left side and simultaneously copy mirror of the left side to the right side.\nFor example, if the given number is \u201C1 2 9 2 1\u201D, we increment 9 to 10 and propagate the carry. So the number becomes \u201C1 3 0 3 1\u201D\n\nCase 2: There are digits left between left side and right side which are not same. So, we just mirror the left side to the right side & try to minimize the number formed to guarantee the next smallest palindrome.\nIn this case, there can be two sub-cases.\n\n2.1) Copying the left side to the right side is sufficient, we don\u2019t need to increment any digits and the result is just mirror of left side. Following are some examples of this sub-case.\nNext palindrome for \u201C7 8 3 3 2 2\u2033 is \u201C7 8 3 3 8 7\u201D\nNext palindrome for \u201C1 2 5 3 2 2\u2033 is \u201C1 2 5 5 2 1\u201D\nNext palindrome for \u201C1 4 5 8 7 6 7 8 3 2 2\u2033 is \u201C1 4 5 8 7 6 7 8 5 4 1\u201D\nHow do we check for this sub-case? All we need to check is the digit just after the ignored part in step 1. This digit is highlighted in above examples. If this digit is greater than the corresponding digit in right side digit, then copying the left side to the right side is sufficient and we don\u2019t need to do anything else.\n\n2.2) Copying the left side to the right side is NOT sufficient. This happens when the above defined digit of left side is smaller. Following are some examples of this case.\nNext palindrome for \u201C7 1 3 3 2 2\u2033 is \u201C7 1 4 4 1 7\u201D\nNext palindrome for \u201C1 2 3 4 6 2 8\u2033 is \u201C1 2 3 5 3 2 1\u201D\nNext palindrome for \u201C9 4 1 8 7 9 7 8 3 2 2\u2033 is \u201C9 4 1 8 8 0 8 8 1 4 9\u201D\nWe handle this subcase like Case 1. We just add 1 to the middle digit (or digits in ase n is even) propagate the carry towards MSB digit of left side and simultaneously copy mirror of the left side to the right side.\n\nRef: www.geeksforgeeks.org.\n\nThis is the way to get **all palindrome** number. For this problem to solve you can consider only **odd palindrome** for fast result.\n\nHere is my implementation, \n\n```\nclass Solution {\n\n    int getNextPalindrome( int nn )\n    {\n        string ss = to_string(nn);\n        int i, j, len = ss.length();\n\n        for(i=0; i<len; i++) if(ss[i] != \'9\') break;\n\n        if(i==len) return (nn+2);       //  all are 9\'s\n\n        //  when not all are 9\'s\n\n        int mid = len/2;        // find the index of mid digit\n\n        // A bool variable to check if copy of left side to right is sufficient or not\n        bool leftIsLess = false;\n\n        i = mid - 1;\n\n        if(len%2) j = mid+1;    //  for odd length palindrome\n        else j = mid;           //  for even length palindrome\n\n        // Initially, ignore the middle same digits\n        while (i >= 0 && ss[i] == ss[j]) i--,j++;\n        \n\n        // Find if the middle digit(s) need to be incremented or not (or copying left\n        // side is not sufficient)\n        if ( i < 0 || ss[i] < ss[j]) leftIsLess = true;\n        \n        \n        // Copy the mirror of left to right\n    \n        while (i >= 0) ss[j++] = ss[i--];\n       \n\n        // Handle the case where middle digit(s) must be incremented.\n        // This part of code is for CASE 1 and CASE 2.2\n        \n        if (leftIsLess == true)\n        {\n            int carry = 1;\n            i = mid - 1;\n\n            // If there are odd digits, then increment\n            // the middle digit and store the carry\n            if (len%2 == 1)\n            {\n                j = mid+1;\n                \n                if(ss[mid]<=\'8\') {ss[mid]++; carry=0;}\n                \n                else ss[mid] = \'0\';               \n            }\n\n            else j = mid;\n         \n            // Add 1 to the rightmost digit of the left side, propagate the carry\n            // towards MSB digit and simultaneously copying mirror of the left side\n            // to the right side.\n            \n            while (i >= 0 && carry)\n            {\n                if(ss[i]<=\'8\') {ss[i]++; ss[j++] = ss[i--]; break;} \n\n                else { \n                    ss[i] = \'0\';     \n                                    \n                    ss[j++] = ss[i--]; \n                }\n            }\n        }\n        \n        return stoi(ss);\n}\n\nbool isprime(int num)\n{\n\n    int j=sqrt((double)(num));\n\n    for(int i=2; i<=j; i++) if(!(num%i)) return false;\n\n    return true;\n\n}\n   \n    \npublic:\n       \n    int primePalindrome(int N) {\n\n        if(N==1) return 2;\n        \n        \n        string ss = to_string(N);\n        int i, j, len = ss.length();\n        \n        int num=N;\n        \n        bool palindrome=true;\n        \n        for(i=0, j=len-1; i<j; i++, j--) if(ss[i]!=ss[j]) {palindrome=false; break;}\n                   \n        if(!palindrome) num = getNextPalindrome(num);\n            \n        while(!isprime(num)) num = getNextPalindrome(num);\n            \n\n    return num;\n}\n};\n```\n
[]