Complete Prime Number solution and explanation
4 more videos on this problem
3765. Complete Prime Number | Biweekly Contest 171 | LeetcodeRapid Syntax · 10:59 · 236 views
3765. Complete Prime Number (Leetcode Medium)Programming Live with Larry · 5:31 · 105 views
LeetCode 3765 | Complete Prime Number | Prefix-Suffix | JavaCode Kage · 6:51 · 64 views
3765. Complete Prime Number #leetcodequestionandanswers #googleinterview #leetcode #dsa #googleCodeVia · 3:12 · 30 views
LeetCode Biweekly Contest 171 | LeetCode 3765 | LeetCode 3766 | LeetCode 3767codeTips · 20:43 · 26 views
The problem
You are given an integer num.
A number num is called a Complete Prime Number if every prefix and every suffix of num is prime.
Return true if num is a Complete Prime Number, otherwise return false.
Note:
- A prefix of a number is formed by the first
kdigits of the number. - A suffix of a number is formed by the last
kdigits of the number. - Single-digit numbers are considered Complete Prime Numbers only if they are prime.
Example 1:
Input: num = 23
Output: true
Explanation:
- Prefixes of
num = 23are 2 and 23, both are prime. - Suffixes of
num = 23are 3 and 23, both are prime. - All prefixes and suffixes are prime, so 23 is a Complete Prime Number and the answer is
true.
Example 2:
Input: num = 39
Output: false
Explanation:
- Prefixes of
num = 39are 3 and 39. 3 is prime, but 39 is not prime. - Suffixes of
num = 39are 9 and 39. Both 9 and 39 are not prime. - At least one prefix or suffix is not prime, so 39 is not a Complete Prime Number and the answer is
false.
Example 3:
Input: num = 7
Output: true
Explanation:
- 7 is prime, so all its prefixes and suffixes are prime and the answer is
true.
Constraints:
1 <= num <= 109
Approach overview
Problem Overview: A number is called a Complete Prime Number if the number itself is prime and every prefix formed by removing digits from the right is also prime. For example, if n = 233, then 233, 23, and 2 must all be prime. The task is to verify whether a given integer satisfies this property.
Approach 1: Prefix Enumeration with Primality Test (O(d * sqrt(n)) time, O(1) space)
Use a mathematical primality test while iteratively removing digits from the number. Start with the full number n. Check if it is prime using a standard sqrt(n) divisor test. If it is prime, remove the last digit using integer division (n //= 10) and repeat the process for the prefix. Continue until the value becomes zero. If any prefix is not prime, the number fails the condition. This approach works because a number with d digits generates at most d prefixes, and each prefix check uses a standard prime test.
The key insight is that you do not need to generate all substrings or convert digits repeatedly. Integer division naturally produces each prefix. The primality check only needs to test divisors up to sqrt(x), which keeps the check efficient even for larger inputs.
This method relies purely on Math and basic Number Theory. Enumeration is limited to digit prefixes rather than scanning a large numeric range, which keeps the runtime predictable.
Approach 2: Optimized Primality with Early Elimination (O(d * sqrt(n)) time, O(1) space)
You can reduce unnecessary checks by eliminating obvious non‑prime prefixes early. If any prefix ends with an even digit or 5 (except the single-digit primes), it cannot be prime. Perform this quick digit check before running the full divisor loop. Then apply the same prefix iteration using integer division. While the asymptotic complexity remains O(d * sqrt(n)), in practice it skips many expensive primality checks.
This variant still uses the same core idea: iterate through prefixes and verify primality. The difference is practical optimization based on number properties. The solution still relies on mathematical reasoning rather than complex data structures.
Recommended for interviews: The prefix enumeration with a standard primality test is the expected approach. It clearly demonstrates understanding of digit manipulation, divisor-based prime checking, and efficient enumeration. Mentioning quick digit-based pruning is a good follow-up optimization, but the main goal is showing a clean prefix iteration with correct time complexity.
Solution
We define a function is_prime(x) to determine whether a number x is prime. Specifically, if x < 2, then x is not prime; otherwise, we check all integers i from 2 to \sqrt{x}. If there exists some i that divides x, then x is not prime; otherwise, x is prime.
Next, we convert the integer num to a string s, and sequentially check whether the integer corresponding to each prefix and suffix of s is prime. For prefixes, we construct the integer x from left to right; for suffixes, we construct the integer x from right to left. If during the checking process we find that the integer corresponding to some prefix or suffix is not prime, we return false; if all integers corresponding to prefixes and suffixes are prime, we return true.
The time complexity is O(\sqrt{n} times log n), and the space complexity is O(log n), where n is the value of the integer num.
class Solution:
def completePrime(self, num: int) -> bool:
def is_prime(x: int) -> bool:
if x < 2:
return False
return all(x % i for i in range(2, int(sqrt(x)) + 1))
s = str(num)
x = 0
for c in s:
x = x * 10 + int(c)
if not is_prime(x):
return False
x, p = 0, 1
for c in s[::-1]:
x = p * int(c) + x
p *= 10
if not is_prime(x):
return False
return Trueclass Solution {
public boolean completePrime(int num) {
char[] s = String.valueOf(num).toCharArray();
int x = 0;
for (int i = 0; i < s.length; i++) {
x = x * 10 + (s[i] - '0');
if (!isPrime(x)) {
return false;
}
}
x = 0;
int p = 1;
for (int i = s.length - 1; i >= 0; i--) {
x = p * (s[i] - '0') + x;
p *= 10;
if (!isPrime(x)) {
return false;
}
}
return true;
}
private boolean isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
}class Solution {
public:
bool completePrime(int num) {
auto isPrime = [&](int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
};
string s = to_string(num);
int x = 0;
for (char c : s) {
x = x * 10 + (c - '0');
if (!isPrime(x)) {
return false;
}
}
x = 0;
int p = 1;
for (int i = (int) s.size() - 1; i >= 0; --i) {
x = p * (s[i] - '0') + x;
p *= 10;
if (!isPrime(x)) {
return false;
}
}
return true;
}
};function completePrime(num: number): boolean {
const isPrime = (x: number): boolean => {
if (x < 2) return false;
for (let i = 2; i * i <= x; i++) {
if (x % i === 0) {
return false;
}
}
return true;
};
const s = String(num);
let x = 0;
for (let i = 0; i < s.length; i++) {
x = x * 10 + (s.charCodeAt(i) - 48);
if (!isPrime(x)) {
return false;
}
}
x = 0;
let p = 1;
for (let i = s.length - 1; i >= 0; i--) {
x = p * (s.charCodeAt(i) - 48) + x;
p *= 10;
if (!isPrime(x)) {
return false;
}
}
return true;
}func completePrime(num int) bool {
isPrime := func(x int) bool {
if x < 2 {
return false
}
for i := 2; i*i <= x; i++ {
if x%i == 0 {
return false
}
}
return true
}
s := strconv.Itoa(num)
x := 0
for i := 0; i < len(s); i++ {
x = x*10 + int(s[i]-'0')
if !isPrime(x) {
return false
}
}
x = 0
p := 1
for i := len(s) - 1; i >= 0; i-- {
x = p*int(s[i]-'0') + x
p *= 10
if !isPrime(x) {
return false
}
}
return true
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Enumeration with Primality Test | O(d * sqrt(n)) | O(1) | General solution for checking whether a number is a complete prime |
| Enumeration with Early Digit Pruning | O(d * sqrt(n)) | O(1) | When many prefixes can be rejected quickly using digit rules |
Frequently asked questions
Is Complete Prime Number easy or hard?
The difficulty is usually classified as Medium because it combines two concepts: efficient prime checking and digit prefix enumeration. The implementation is short, but recognizing that every prefix must also be prime is the key insight.
Complete Prime Number Python/Java solution
In Python or Java, repeatedly check if the current number is prime and then divide it by 10 to remove the last digit. Implement a helper function that tests divisibility from 2 up to sqrt(x). Repeat until the number becomes zero or a non‑prime prefix is found.
How to solve Complete Prime Number in O(n)?
The problem typically does not require scanning up to n. Instead, check each digit prefix of the number directly. Using prefix enumeration and a square‑root primality test results in O(d * sqrt(n)) time, which is efficient for typical integer limits.
What is the best approach for Complete Prime Number?
The most practical approach is prefix enumeration combined with a primality test. Start with the full number, check if it is prime, then repeatedly remove the last digit and check each prefix. If every prefix is prime, the number is a complete prime. This runs in O(d * sqrt(n)) time where d is the number of digits.
Is Complete Prime Number asked at Google/Amazon/Meta?
Prime number variations and prefix‑based number checks appear frequently in coding interviews at companies like Google and Amazon. While the exact problem name may vary, interviewers often test understanding of primality testing, digit manipulation, and mathematical reasoning.
What data structure is used in Complete Prime Number?
No complex data structure is required. The solution relies on mathematical operations such as integer division and a loop for primality testing. The focus is on number theory rather than arrays, stacks, or hash maps.
What is the time complexity of Complete Prime Number?
The standard solution runs in O(d * sqrt(n)) time and O(1) space. A number with d digits produces at most d prefixes, and each prefix requires a primality check up to sqrt(value). Since only integer operations are used, the memory overhead stays constant.