Leetcode 866: Prime Palindrome
Given an integer
n, find the smallest integer that is both a prime number and a palindrome, and is greater than or equal to n. A prime number is an integer greater than 1 with no divisors other than 1 and itself. A palindrome is a number that reads the same forwards and backwards.Problem
Approach
Steps
Complexity
Input: The input is a single integer `n`.
Example: Input: n = 15
Constraints:
• 1 <= n <= 10^8
Output: Return the smallest integer that is both a prime and a palindrome, and is greater than or equal to `n`.
Example: Output: 17
Constraints:
• The output will always exist within the range [2, 2 * 10^8].
Goal: Find the smallest prime palindrome greater than or equal to the given integer `n`.
Steps:
• Iterate over integers starting from `n`.
• Check if the current number is a palindrome.
• If it is a palindrome, check if it is a prime number.
• If both conditions are satisfied, return the number.
Goal: Ensure correctness while adhering to time and space limits.
Steps:
• The function must handle numbers up to 10^8 efficiently.
• Palindromes and primes should be checked systematically.
Assumptions:
• The input `n` is a valid positive integer.
• The answer always exists within the given range.
• Input: Input: n = 15, Output: 17
• Explanation: The smallest palindrome greater than or equal to 15 is 17, and 17 is also a prime number.
• Input: Input: n = 22, Output: 101
• Explanation: The smallest palindrome greater than or equal to 22 that is also prime is 101.
Approach: The problem is solved by combining palindrome generation with primality testing for numbers starting from the input value.
Observations:
• Palindromes can be generated by mirroring a number's digits.
• Primality testing can be optimized by only checking divisors up to the square root.
• Special cases include small values like 1 and 2.
• Start generating palindromes greater than or equal to `n` and test them for primality.
Steps:
• Handle small cases where `n <= 11` directly.
• Iterate over integers `x` to generate palindromes by mirroring the digits.
• Check if the generated palindrome is greater than or equal to `n`.
• For each palindrome, check if it is a prime number.
• Return the first number that satisfies both conditions.
Empty Inputs:
• Not applicable since `n` is always provided.
Large Inputs:
• Input `n` close to 10^8, requiring efficient palindrome and prime checks.
Special Values:
• Input `n = 1`, where the output should be 2.
• Input `n = 8`, where the output is the special palindrome prime 11.
Constraints:
• Ensure the function does not generate unnecessary numbers or exceed time limits.
int primePalindrome(int n) {
if(8 <= n && n <= 11) return 11;
for(int x = 1; x < 100000; x++) {
string s = to_string(x), r(s.rbegin(), s.rend());
int y = stoi(s + r.substr(1));
if(y >= n && isPrime(y)) return y;
}
return -1;
}
bool isPrime(int num) {
if(num < 2 || num %2 == 0) return num == 2;
for(int i = 3; i * i <= num; i += 2) {
if(num%i == 0) return false;
}
return true;
}
1 : Function Definition
int primePalindrome(int n) {
The function definition of `primePalindrome` that takes an integer n as input and returns an integer.
2 : Condition Check
if(8 <= n && n <= 11) return 11;
A base case for small numbers between 8 and 11. It returns 11 directly since 11 is the smallest prime palindrome in that range.
3 : Loop
for(int x = 1; x < 100000; x++) {
A loop iterates over integers starting from 1 to 100,000, generating potential candidates for prime palindromes.
4 : String Operations
string s = to_string(x), r(s.rbegin(), s.rend());
Converts the integer x to a string and generates its reverse by using the `rbegin()` and `rend()` iterators.
5 : String Concatenation
int y = stoi(s + r.substr(1));
Concatenates the string `s` and the substring of `r` (excluding its first character) to form a potential palindrome number y.
6 : Prime Check
if(y >= n && isPrime(y)) return y;
Checks if the number y is greater than or equal to n and if it is prime, in which case it is returned as the result.
7 : Loop End
}
End of the loop iterating over potential palindrome numbers.
8 : Return Statement
return -1;
If no prime palindrome is found in the loop, the function returns -1 to indicate failure.
9 : Function End
}
End of the `primePalindrome` function.
10 : Function Definition
bool isPrime(int num) {
The definition of the helper function `isPrime`, which checks if a number is prime.
11 : Prime Condition Check
if(num < 2 || num %2 == 0) return num == 2;
Checks if the number is less than 2 or even. If so, it only returns true for the number 2.
12 : Loop For Prime
for(int i = 3; i * i <= num; i += 2) {
A loop iterating from 3 to the square root of `num`, checking if `num` is divisible by any odd number.
13 : Prime Check Return False
if(num%i == 0) return false;
If `num` is divisible by `i`, then it is not prime and the function returns false.
14 : Prime Check Return True
}
End of the loop checking for prime factors.
15 : Function End
return true;
If no factors are found, the function returns true, indicating that `num` is prime.
16 : Function End
}
End of the `isPrime` function.
Best Case: O(sqrt(N)), where N is the smallest valid output.
Average Case: O(M * sqrt(N)), where M is the number of candidates generated.
Worst Case: O(M * sqrt(N)), when `n` is large and close to 10^8.
Description: Palindrome generation is efficient, but primality testing contributes the most to complexity.
Best Case: O(1), when considering only constant space for variables.
Worst Case: O(log(N)), where N is the palindrome being checked.
Description: Space usage is minimal as palindrome generation and primality testing use iterative methods.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus