Complete Prime Number

Difficulty: Medium

Topics: Math, String, Primality Test

Companies: Google, Amazon, Microsoft

Pro Tip: A number is a complete prime if and only if all its prefixes and suffixes are prime numbers. The key optimization is to avoid redundant prime checks by memoization.

Problem Statement

Given an integer num, return true if it is a complete prime, otherwise return false. A complete prime is a number where every prefix and every suffix of its decimal representation is a prime number.

Example 1

Input: num = 233

Output: true

Explanation: Prefixes: 2, 23, 233 (all prime). Suffixes: 3, 33, 233 (all prime).

Example 2

Input: num = 19

Output: false

Explanation: Prefix 1 is not prime. Suffix 9 is not prime.

Example 3

Input: num = 5

Output: true

Explanation: Single digit prime number.

Problem Link: View on LeetCode ↗

Key Insight

The solution relies on these crucial observations:

A number is a complete prime if ALL its prefixes and suffixes are prime numbers
Single-digit numbers must be prime (2, 3, 5, 7)
Prefixes are formed from left to right, suffixes from right to left
The same number may appear as both prefix and suffix (the full number)
We can optimize by memoizing prime checks to avoid redundant computations

Important: The number 1 is NOT prime. Also, leading zeros are not considered (since we're working with actual integer values).

Approach 1: Naive Prefix-Suffix Check (Your Approach)

Check all prefixes and suffixes independently by converting substrings to integers and testing primality.

Algorithm Steps

Convert number to string for easy substring operations
Check all prefixes from left to right:
- Take substring from index 0 to i (inclusive)
- Convert to integer and check primality
- If any prefix is not prime, return false
Check all suffixes from right to left:
- Take substring from index i to end
- Convert to integer and check primality
- If any suffix is not prime, return false
If all checks pass, return true

Complexity Analysis

Time Complexity	Space Complexity
O(n²√M)	O(1)

Where n is number of digits and M is the maximum number value. Each primality test takes O(√num) time.

Naive Prefix-Suffix Check

class Solution {
public:
    
    bool isPrime(int num) {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    bool completePrime(int num) {
        string s = to_string(num);
        int n = s.length();
        
        // Check all prefixes
        string prefix = "";
        for (int i = 0; i < n; i++) {
            prefix += s[i];
            int val = stoi(prefix);
            if (!isPrime(val)) return false;
        }
        
        // Check all suffixes
        string suffix = "";
        for (int i = n - 1; i >= 0; i--) {
            suffix = s[i] + suffix;
            int val = stoi(suffix);
            if (!isPrime(val)) return false;
        }
        
        return true;
    }
};

class Solution {
    
    private boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public boolean completePrime(int num) {
        String s = Integer.toString(num);
        int n = s.length();
        
        // Check all prefixes
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < n; i++) {
            prefix.append(s.charAt(i));
            int val = Integer.parseInt(prefix.toString());
            if (!isPrime(val)) return false;
        }
        
        // Check all suffixes
        StringBuilder suffix = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            suffix.insert(0, s.charAt(i));
            int val = Integer.parseInt(suffix.toString());
            if (!isPrime(val)) return false;
        }
        
        return true;
    }
}

class Solution:
    
    def isPrime(self, num: int) -> bool:
        if num <= 1:
            return False
        if num == 2:
            return True
        if num % 2 == 0:
            return False
        
        for i in range(3, int(num**0.5) + 1, 2):
            if num % i == 0:
                return False
        return True
    
    def completePrime(self, num: int) -> bool:
        s = str(num)
        n = len(s)
        
        # Check all prefixes
        prefix = ""
        for i in range(n):
            prefix += s[i]
            if not self.isPrime(int(prefix)):
                return False
        
        # Check all suffixes
        suffix = ""
        for i in range(n - 1, -1, -1):
            suffix = s[i] + suffix
            if not self.isPrime(int(suffix)):
                return False
        
        return True

Efficiency: This approach is straightforward but may perform redundant prime checks for the same number appearing as both prefix and suffix.

Approach 2: Memoized Prime Checks

Use memoization (caching) to avoid redundant prime number checks for the same value.

Algorithm Steps

Create a memoization map/dictionary to store prime check results
Convert number to string for substring operations
Generate all unique prefixes and suffixes
For each unique number, check primality using memoized function
Return false if any check fails, otherwise return true

Complexity Analysis

Time Complexity	Space Complexity
O(k√M)	O(k)

Where k is number of unique prefixes/suffixes (≤ 2n) and M is maximum number value.

Memoized Prime Checks

class Solution {
public:
    
    unordered_map<int, bool> memo;
    
    bool isPrime(int num) {
        if (memo.find(num) != memo.end()) {
            return memo[num];
        }
        
        if (num <= 1) {
            memo[num] = false;
            return false;
        }
        if (num == 2) {
            memo[num] = true;
            return true;
        }
        if (num % 2 == 0) {
            memo[num] = false;
            return false;
        }
        
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                memo[num] = false;
                return false;
            }
        }
        
        memo[num] = true;
        return true;
    }
    
    bool completePrime(int num) {
        string s = to_string(num);
        int n = s.length();
        
        unordered_set<int> numbersToCheck;
        
        // Collect all prefixes
        string prefix = "";
        for (int i = 0; i < n; i++) {
            prefix += s[i];
            numbersToCheck.insert(stoi(prefix));
        }
        
        // Collect all suffixes
        string suffix = "";
        for (int i = n - 1; i >= 0; i--) {
            suffix = s[i] + suffix;
            numbersToCheck.insert(stoi(suffix));
        }
        
        // Check all unique numbers
        for (int number : numbersToCheck) {
            if (!isPrime(number)) {
                return false;
            }
        }
        
        return true;
    }
};

import java.util.*;

class Solution {
    
    private Map<Integer, Boolean> memo = new HashMap<>();
    
    private boolean isPrime(int num) {
        if (memo.containsKey(num)) {
            return memo.get(num);
        }
        
        if (num <= 1) {
            memo.put(num, false);
            return false;
        }
        if (num == 2) {
            memo.put(num, true);
            return true;
        }
        if (num % 2 == 0) {
            memo.put(num, false);
            return false;
        }
        
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                memo.put(num, false);
                return false;
            }
        }
        
        memo.put(num, true);
        return true;
    }
    
    public boolean completePrime(int num) {
        String s = Integer.toString(num);
        int n = s.length();
        
        Set<Integer> numbersToCheck = new HashSet<>();
        
        // Collect all prefixes
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < n; i++) {
            prefix.append(s.charAt(i));
            numbersToCheck.add(Integer.parseInt(prefix.toString()));
        }
        
        // Collect all suffixes
        StringBuilder suffix = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            suffix.insert(0, s.charAt(i));
            numbersToCheck.add(Integer.parseInt(suffix.toString()));
        }
        
        // Check all unique numbers
        for (int number : numbersToCheck) {
            if (!isPrime(number)) {
                return false;
            }
        }
        
        return true;
    }
}

class Solution:
    
    def __init__(self):
        self.memo = {}
    
    def isPrime(self, num: int) -> bool:
        if num in self.memo:
            return self.memo[num]
        
        if num <= 1:
            self.memo[num] = False
            return False
        if num == 2:
            self.memo[num] = True
            return True
        if num % 2 == 0:
            self.memo[num] = False
            return False
        
        for i in range(3, int(num**0.5) + 1, 2):
            if num % i == 0:
                self.memo[num] = False
                return False
        
        self.memo[num] = True
        return True
    
    def completePrime(self, num: int) -> bool:
        s = str(num)
        n = len(s)
        
        numbers_to_check = set()
        
        # Collect all prefixes
        prefix = ""
        for i in range(n):
            prefix += s[i]
            numbers_to_check.add(int(prefix))
        
        # Collect all suffixes
        suffix = ""
        for i in range(n - 1, -1, -1):
            suffix = s[i] + suffix
            numbers_to_check.add(int(suffix))
        
        # Check all unique numbers
        for number in numbers_to_check:
            if not self.isPrime(number):
                return False
        
        return True

Advantage: This approach reduces redundant prime checks by storing results in a memoization cache, improving performance when the same number appears multiple times.

Approach 3: Optimized Early Exit with Set

Combine prefix and suffix checking with early exit and use a set to track checked numbers.

Algorithm Steps

Convert number to string
Use a set to track numbers that have been checked
Check prefixes first, exiting early if any fail
Then check suffixes, using memoized results when available
Return true only if all checks pass

Complexity Analysis

Time Complexity	Space Complexity
O(n√M)	O(n)

Where n is number of digits and M is maximum number value.

Optimized Early Exit

class Solution {
public:
    
    bool isPrime(int num) {
        if (num <= 1) return false;
        if (num == 2 || num == 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        
        // 6k ± 1 optimization
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
    
    bool completePrime(int num) {
        string s = to_string(num);
        int n = s.length();
        
        unordered_set<int> checked;
        
        // Check prefixes with early exit
        for (int i = 0; i < n; i++) {
            int prefix = stoi(s.substr(0, i + 1));
            if (checked.find(prefix) == checked.end()) {
                if (!isPrime(prefix)) return false;
                checked.insert(prefix);
            }
        }
        
        // Check suffixes with early exit and reuse checked results
        for (int i = n - 1; i >= 0; i--) {
            int suffix = stoi(s.substr(i));
            if (checked.find(suffix) == checked.end()) {
                if (!isPrime(suffix)) return false;
                checked.insert(suffix);
            }
        }
        
        return true;
    }
};

import java.util.*;

class Solution {
    
    private boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num == 2 || num == 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        
        // 6k ± 1 optimization
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
    
    public boolean completePrime(int num) {
        String s = Integer.toString(num);
        int n = s.length();
        
        Set<Integer> checked = new HashSet<>();
        
        // Check prefixes with early exit
        for (int i = 0; i < n; i++) {
            int prefix = Integer.parseInt(s.substring(0, i + 1));
            if (!checked.contains(prefix)) {
                if (!isPrime(prefix)) return false;
                checked.add(prefix);
            }
        }
        
        // Check suffixes with early exit and reuse checked results
        for (int i = n - 1; i >= 0; i--) {
            int suffix = Integer.parseInt(s.substring(i));
            if (!checked.contains(suffix)) {
                if (!isPrime(suffix)) return false;
                checked.add(suffix);
            }
        }
        
        return true;
    }
}

class Solution:
    
    def isPrime(self, num: int) -> bool:
        if num <= 1:
            return False
        if num == 2 or num == 3:
            return True
        if num % 2 == 0 or num % 3 == 0:
            return False
        
        # 6k ± 1 optimization
        i = 5
        while i * i <= num:
            if num % i == 0 or num % (i + 2) == 0:
                return False
            i += 6
        return True
    
    def completePrime(self, num: int) -> bool:
        s = str(num)
        n = len(s)
        
        checked = set()
        
        # Check prefixes with early exit
        for i in range(n):
            prefix = int(s[:i + 1])
            if prefix not in checked:
                if not self.isPrime(prefix):
                    return False
                checked.add(prefix)
        
        # Check suffixes with early exit and reuse checked results
        for i in range(n - 1, -1, -1):
            suffix = int(s[i:])
            if suffix not in checked:
                if not self.isPrime(suffix):
                    return False
                checked.add(suffix)
        
        return True

Optimization: This approach uses the 6k ± 1 optimization for primality testing and early exit strategy, making it the most efficient among all approaches.

Edge Cases and Testing

1. Single Digit Numbers

Input: 2 → Output: true (prime)
Input: 4 → Output: false (not prime)
Input: 1 → Output: false (not prime)

2. Two Digit Numbers

Input: 23 → Output: true (prefixes: 2,23; suffixes: 3,23 - all prime)
Input: 29 → Output: true (prefixes: 2,29; suffixes: 9,29 - 9 not prime → false)
Input: 19 → Output: false (prefix 1 not prime)

3. Three Digit Numbers

Input: 233 → Output: true (all prefixes and suffixes prime)
Input: 237 → Output: false (suffix 37 prime, but 7 prime, 237 not prime? Let's check)
Actually: Prefixes: 2,23,237 (237 not prime → false)
Suffixes: 3,37,237 (237 not prime → false)

4. Numbers with Repeated Digits

Input: 373 → Output: true
Prefixes: 3,37,373 (all prime)
Suffixes: 3,73,373 (all prime)

Input: 777 → Output: false
Prefixes: 7,77,777 (77 not prime, 777 not prime)

5. Large Numbers

Input: 233993 → Output: true
Prefixes: 2,23,233,2339,23399,233993 (all prime)
Suffixes: 3,93,993,3993,33993,233993 (need to check each)

Important: Always test with single-digit numbers, numbers containing digit 1, and numbers where middle prefixes/suffixes might fail even if the full number is prime.

Detailed Explanation

The problem requires checking if a number is a "complete prime" - meaning ALL its prefixes and ALL its suffixes must be prime numbers.

For the number 233993:

Prefixes: 2, 23, 233, 2339, 23399, 233993
Suffixes: 3, 93, 993, 3993, 33993, 233993
All must be prime for the number to be a complete prime

The key challenge is efficiently checking primality for potentially many numbers. We can optimize by:

Memoization: Store results of primality tests to avoid redundant computations
Early Exit: Return false as soon as any prefix or suffix fails the prime test
Optimized Primality Test: Use 6k ± 1 optimization to check fewer divisors
Set Usage: Track already checked numbers to avoid duplicate checks

The most efficient approach (Approach 3) combines all these optimizations:

Uses 6k ± 1 optimization for faster primality testing
Implements early exit when any check fails
Uses a set to avoid redundant prime checks
Processes prefixes and suffixes separately for clarity

Why it works: A number is a complete prime if and only if every possible substring starting from the beginning (prefix) and every possible substring ending at the end (suffix) represents a prime number when interpreted as an integer.

FAQs

1. What is the definition of a complete prime?

A complete prime is a number where every prefix (substring starting from the first digit) and every suffix (substring ending at the last digit) of its decimal representation is a prime number.

2. Is 1 considered a prime number in this problem?

No, 1 is not considered a prime number. According to standard mathematical definition, a prime number must be greater than 1 and have exactly two distinct positive divisors: 1 and itself.

3. What is the time complexity of the primality test?

The basic primality test has time complexity O(√n) where n is the number being tested. The optimized 6k ± 1 version reduces the constant factor but remains O(√n).

4. Why use memoization for prime checks?

Memoization avoids redundant primality tests for the same number. For example, the full number appears as both a prefix and suffix, and smaller numbers may appear multiple times in different contexts.

5. What is the 6k ± 1 optimization for primality testing?

All prime numbers greater than 3 can be expressed in the form 6k ± 1. This optimization checks divisibility only by numbers of this form, reducing the number of checks by about 2/3 compared to checking all numbers up to √n.

6. Can leading zeros appear in prefixes or suffixes?

No, since we're converting substrings to integers, leading zeros are automatically removed. For example, "01" becomes 1, which would then be tested for primality.

7. What is the maximum number of digits we need to handle?

The problem constraints typically limit numbers to 32-bit integers (up to 2,147,483,647 or about 10 digits). However, our solutions work for any integer that fits in the language's integer type.

8. How does early exit improve performance?

Early exit means we stop checking as soon as we find any prefix or suffix that is not prime. This can significantly reduce the number of primality tests needed, especially for numbers that fail early.

9. Are there any known complete primes?

Yes, some known complete primes include: 2, 3, 5, 7, 23, 37, 53, 73, 373, 233993, etc. The sequence is finite and known as "truncatable primes" in mathematics.

10. What's the difference between prefix and suffix in this context?

Prefix: Substring starting from the first digit (e.g., for 2357: 2, 23, 235, 2357). Suffix: Substring ending at the last digit (e.g., for 2357: 7, 57, 357, 2357). Both must be prime for a complete prime.

About Algopush:Algopush provides comprehensive algorithm solutions and explanations for coding interview preparation. Visit algopush.com for more problem solutions and coding resources.