Prime Palindrome LeetCode Həlli

Çətinlik səviyyəsi MühitBaxılıb 68

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Prime Palindrome LeetCode Həlli - Bizə tam ədəd verilir və ən kiçik əsası qaytarmağımız xahiş olunur. palindrom verilmiş 'n' tam ədədinə bərabər və ya böyükdür.

Tam ədəddir baş tam olaraq iki bölən varsa: 1 və özü. Qeyd edək ki, 1 a deyil baş nömrə.

  • Məsələn, 2, 3, 5, 7, 11 və 13 sadə ədədlərdir.

Tam ədəd adır palindrom sağdan sola oxuduğu kimi soldan sağa oxuyursa.

Test nümunələri cavabın həmişə mövcud olması və [2, 2*10^8] diapazonunda olması üçün yaradılır.

Nümunələr və izahatlar

Misal 1:

Input: n = 6
Output: 7
Explanation: 7 is prime & palindrome

Misal 2:
Input: n = 8
Output: 11
Explanation: 9 is palindrome but not prime, 10 is neither prime nor palindrome, hence 11

Misal 3:
Input: n = 13
Output: 101
Explanation: no two digits number can be palindrome with both different digits, eg. palindromes having 2 digits are 22, 33, 44, 55 ..... but none of these are prime.

Yanaşma

Optimallaşdırma ilə Brute-Force

Biz n+1-dən 2*10^8-ə qədər bütün ədədləri təkrarlaya bilərik (çünki sualda cavablar həmişə mövcuddur və [2, 2*10^8] diapazonundadır).

Bununla belə, bu yanaşma TLE-yə səbəb olacaqdır. Bu həlli optimallaşdırmaq üçün [1e7, 1e8] diapazonunda ən kiçik sadə palindromun 100030001 olması faktından istifadə edəcəyik. Buna görə də, əgər n bu diapazonda yerləşirsə, sadəcə olaraq bu ədəddən keçməyə başlayın və hər bir ədədin sadə olub olmadığını yoxlamağa davam edin. palindrom.

Zamanın mürəkkəbliyini daha da azaltmaq üçün heç vaxt ola bilməyəcəyi kimi bütün cüt ədədləri atlaya bilərik baş. Beləliklə, hər təkrarlamada döngədə göstəricini 2 dəfə artırın.

Primallığı və ədədin palindrom olub olmadığını yoxlamaq üçün 2 ayrı funksiyadan istifadə edə bilərik. Primallığın yoxlanılması asan məsələdir, lakin nəzərə alın ki, biz palindromun yoxlanılmasında istifadə olunan əks funksiyanı təyin etdik. Bu funksiya hər dəfə təkrarlamada ədədi 10-a bölür və qalanı saxlayır.

QEYD: biz palindromik xüsusiyyəti yoxlamaq üçün to_string inbuilt funksiyasından istifadə etməmişik. to_String-dən istifadə çox vaxt aparır və TLE ilə nəticələnir.

Kodu

Prime Palindrome LeetCode Həlli üçün C++ kodu

class Solution {
    bool isPrime(int n) {
        for(int i=2; i<=sqrt(n);i++) {
            if(n%i==0) return 0;
        }
        return 1;
    }

    int reverse(int n){
        int m = 0;
        while (n) {
            m = m*10 + n % 10;
            n /= 10;
        }
        return m;
    }
    
    int isPalindrome(int n){
        return n == reverse(n);
    }
public:
    int primePalindrome(int n) {
        if( n <= 2) return 2;
        
        if(n>=1e7 && n<=1e8) {
            n=100030001;
        }
        
        if(n%2==0) n++;
        
        for(int i=n; i>=n; i+=2){
            if(isPalindrome(i)) {
                if(isPrime(i)) return i;
            } 
        }
        return -1;
    }
};

Prime Palindrome LeetCode Solution üçün Java kodu

class Solution {
    private Boolean isPrime(int n) {
        for(int i=2; i<=Math.sqrt(n);i++) {
            if(n%i==0) return false;
        }
        return true;
    }

    private int reverse(int n){
        int m = 0;
        while (n>0) {
            m = m*10 + n % 10;
            n /= 10;
        }
        return m;
    }
    
    private Boolean isPalindrome(int n){
        return n== reverse(n);
    }
    public int primePalindrome(int n) {
        if( n <= 2) return 2;
        
        if(n>=1e7 && n<=1e8) {
            n=100030001;
        }
        
        if(n%2==0) n++;
        
        for(int i=n; i>=n; i+=2){
            if(isPalindrome(i)) 
                if(isPrime(i)) return i;
        }
        return -1;
    }
}

Mürəkkəblik təhlili

  • Zamanın mürəkkəbliyi: O(n*logn*sqrt(n))
    • Döngə O(n/2) vaxtını alaraq n/2 dəfə işləyir, yəni. O(n) Bu, Baş və Palindrom adlı 2 funksiyanı çağırır
    • isPrime O(sqrt(n)) vaxt alır
    • isPalindrome O(logn) vaxtını alır
  • Kosmik mürəkkəblik: O (1)
    • əlavə yer tələb olunmur
Crack Sistemi Dizayn Müsahibələri
Translate »