866. Prime Palindrome
Find the smallest prime palindrome greater than or equal to
N
.Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1.
For example, 2,3,5,7,11 and 13 are primes.
Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.
For example, 12321 is a palindrome.
Example 1:
Input: 6
Output: 7Example 2:
Input: 8
Output: 11Example 3:
Input: 13
Output: 101
Note:
1 <= N <= 10^8
- The answer is guaranteed to exist and be less than
2 * 10^8
.
Approach #1: Math. [Java]
class Solution {
public int primePalindrome(int N) {
if (8 <= N && N <= 11) return 11;
for (int x = 1; x < 100000; ++x) {
String s = Integer.toString(x), r = new StringBuilder(s).reverse().toString().substring(1);
int y = Integer.parseInt(s + r);
if (y >= N && isPrime(y)) return y;
}
return -1;
} boolean isPrime(int x) {
if (x < 2 || x % 2 == 0) return x == 2;
for (int i = 3; i * i <= x; i += 2) {
if (x % i == 0) return false;
}
return true;
}
}
Analysis:
All palindrome with even digits is multiple of 11.
We can prove as follow:
11 % 11 == 0
1111 % 11 == 0
111111 % 11 == 0
11111111 % 11 == 0
So:
1001 % 11 = (1111 - 11 * 10) % 11 == 0
100001 % 11 = (111111 - 1111 * 10) % 11 == 0
10000001 % 11 = (11111111 - 111111 * 10) % 11 == 0
For any palindrome with even digits:
abcddcba % 11
= (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11
= 0
All palindrome with even digits is multiple of 11.
So among them, 11 is the only one prime
if (8 <= N <= 11) return 11
For other cases, we consider only palindrome with odd digits.
Time Complexity:
O(10000) to check all numbers 1 - 10000.
isPrime function is O(sqrt(x)) in worst case.
But only sqrt(N) worst cases for 1 <= x <= N
In general it's O(logx)
Reference:
https://leetcode.com/problems/prime-palindrome/discuss/146798/Search-Palindrome-with-Odd-Digits
最新文章
- AngularJS 中的Promise --- $q服务详解
- jsp基础知识
- php安装gearman扩展实现异步分步式任务
- (09)odoo工作流
- hdu----(1075)What Are You Talking About(trie之查找)
- java的加减乘除
- React-Native OpenGL体验二
- JavaScript数组去重方法及测试结果
- Chrome浏览器扩展开发系列之四:Browser Action类型的Chrome浏览器扩展
- 基于SwiperJs的H5/移动端下拉刷新上拉加载更多的效果
- Oracle问题之字符集问题,登陆sqlplus出现问号
- [Swift]LeetCode13. 罗马数字转整数 | Roman to Integer
- PC逆向之代码还原技术,第一讲基本数据类型在内存中的表现形式.浮点,指针寻址公式
- (译)MySQL的10个基本性能技巧
- 问题 1462: [蓝桥杯][基础练习VIP]Huffuman树
- win7 cmd终端连接android手机运行adb shell脚本命令
- c++类成员变量初始化相关问题
- Github笔记(1)
- Svn 提示错误:previous operation has not finished 解决方案
- centos6安装ElasticSearch5.6.5错误记录