✅Explained Fastest solution || C++ || odd length palindromes
Brute Intuition\n Describe your first thoughts on how to solve this problem. \nIn brute force algorithm, we will iterate over all $i$ for $>=n$ && $<=210^8$ and
# Brute Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn brute force algorithm, we will iterate over all $i$ for $>=n$ && $<=2*10^8$ and check if that is prime and is palindrome or not. \nAs soon as some i satisfies this equation, we will return the i.\n\nTime complexity to find if n is prime or not $O(sqrt(n))$\nTime complexity to find if n is palindrome or not $O(log(n))$\n\nOverall this brute approach will take too much time complexity.\n\nThe optimized solution is deduced from one fact ------\nAll even length palindrome are divisble by 11.\nAnd among all even length palindrome only 11 is prime. \nSo now we have to worry about only odd length palindrome.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nNow, we make such algorithm which only checks for odd length palindrome and checks if that is prime or not.\n\nThis question also teaches us how to print all odd length palindrome efficiently.\n\nBrute way would be to iterate over all possibilities and check if it is odd or not. \n\nThe optimised solution to get only odd length palindrome is by making odd length palindrome.\n\nNow we need to see that the answer lies between $[2,2*10^8]$. \n200000000 ---It is of length 9.\nSo the palindrome will be abcdedcba.\nSo, if we iterate over all abcde, we can make a corresponding palindrome and it will be a odd length too.\nSo by just iterating over abcde, i.e. 10^5. We can create all palindromes less than $2*10^8$ without iteration.\n\n# Individual Complexity\n- Time complexity: $O(100000)*[O(log(i)) + O(log(i)) + O(2*log(i)-1) + sqrt(x)]$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nwhere \ni will be $1<=i<=1e5$\nI checked time complexities of the inbuilt functions also ans \nto_string(i)-------------------->$O(log(i))$\nas there are $log(i)$ digits in integer $i$\nreverse(s.begin(),s.end())-----> $O(log(i))$\nstoi(s)-------------------------> $O(2*(log(i))-1)$ \nas the total length will $log(i)+log(i)-1$\nisprime(x)---------------------> $O(sqrt(x))$\n\n# Overall  Complexity\nTime complexity: $O(100000)*[O(log(i)) + O(log(i)) + O(2*log(i)-1) + sqrt(x)]$\n\n- Space complexity: $O(1)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n  \n    \n    bool isprime(int n)\n    {\n        if(n==0 || n==1) return false;\n        for(int i =2;i*i<=n;i++)\n        {\n            if(n%i==0) return false;\n        }\n        return true;\n    }\n\n    int primePalindrome(int n) \n    {\n        std::ios_base::sync_with_stdio(false);\n        cin.tie(NULL);\n        cout.tie(NULL);\n        if(n>=8 && n<=11) return 11;\n        for(int i =1;i<=100000;i++)\n        {\n            string s = to_string(i); //convert int to string\n            string r =s; \n            reverse(r.begin(),r.end()); //reverse the string and store in r\n            int y = stoi(s+r.substr(1)); //  adding r in s except first character and convering to integer\n            if(y>=n && isprime(y)) return y; // checking if it is prime or not.\n        }\n        return 0;\n    }\n};\n```
['Math', 'Number Theory', 'C++']