गिनती की शर्तें Leetcode Solutions


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब एक राजधानी गूगल माइक्रोसॉफ्ट
hashing मठ

इस समस्या में, हमें एक पूर्णांक दिया जाता है, एन। लक्ष्य यह है कि एन की तुलना में संख्या कितनी कम है, यह निर्धारित करना है। पूर्णांक गैर-नकारात्मक होने के लिए विवश है।

उदाहरण

7
3
10
4

व्याख्या

10 से कम की प्राइम्स 2, 3, 5 और 7. हैं, तो गिनती 4 है।

दृष्टिकोण (जानवर बल)

सामान्य दृष्टिकोण एन से कम प्रत्येक पूर्णांक के लिए जाँच करना और यदि वे प्रधान हैं तो परिणाम में वृद्धि करना है। उदाहरण के लिए, N = 10. पर विचार करें, अब हम इस रेंज में कितने प्राइम झूठ बोलते हैं, यह जानने के लिए हम 2 से N - 1 तक चेक चला सकते हैं। लेकिन, इस दृष्टिकोण के लिए पूरी सीमा पर एक प्रमुख जाँच की आवश्यकता होती है, [२, एन - १]।  इसलिए, यह धीमा है।

हम कुछ अनुकूलन कर सकते हैं जैसे:

  1. 2 के अलावा हर अभाज्य संख्या एक पूर्णांक है। इतना होने के बाद 2, हम केवल अजीब पूर्णांक के लिए जाँच कर सकते हैं।
  2. हम जांच सकते हैं कि कोई संख्या मुख्य है या नहीं O (√N) एल्गोरिथ्म में सुधार करने का समय।

हालाँकि, हमारे पास अभी भी एक बेहतर दृष्टिकोण है, इस लेख में बाद में चर्चा की गई है।

कलन विधि

  1. यदि संख्या से कम है 3, वापसी 0, जैसा कि 2 सबसे छोटा प्राइम है
  2. 3 से शुरू होकर सभी नंबरों की जाँच करें एक लूप चलाएं
  3. एक संख्या, N प्रमुख है अगर:
    • यह है 2 और के बीच मुख्य कारक के √ N
  4. यदि संख्या प्रधान है, तो वेतन वृद्धि परिणाम
  5. परिणाम प्रिंट करें

गणना की शर्तों Leetcode समाधान का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int N)
{
    for(int i = 2 ; i * i <= N ; i++)
        if(N % i == 0)
            return false;
    return true;
}


int countPrimes(int N)
{
    if(N < 3)
        return 0;
    int cnt = 1;
    for(int i = 3 ; i < N ; i += 2)
        if(isPrime(i))
            cnt++;

    return cnt;
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

जावा प्रोग्राम

class count_primes
{
    static boolean isPrime(int N)
    {
        for(int i = 2 ; i * i <= N ; i++)
            if(N % i == 0)
                return false;

        return true;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        int cnt = 1;//since number is atleast 3, 2 is a prime less than N
        for(int i = 3 ; i < N ; i += 2)
            if(isPrime(i))
                cnt++;
        return cnt;
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

काउंट प्राइम्स Leetcode Solutions की जटिलता विश्लेषण

समय जटिलता

हम एक लूप चलाते हैं एन / एक्सएनयूएमएक्स समय। प्रत्येक जांच में, जटिलता ओ (एन / 2) का समय (औसत के रूप में लेना) एन / २) खर्च हो चुका है। तो, इस एल्गोरिथ्म की समय जटिलता है O (N√N)।

अंतरिक्ष की जटिलता

ओ (1), केवल निरंतर चर का उपयोग निरंतर चर के लिए किया जाता है।

दृष्टिकोण (इष्टतम विधि)

किसी भी अभाज्य संख्या पर विचार करें, कहने दें 5, फिर यह सुनिश्चित है कि 5 के सभी गुणक, स्वयं के अलावा कभी भी प्रधान नहीं हो सकते क्योंकि उनके 5 में से एक उनके प्रमुख कारक होंगे। इसी तरह, हम सभी संख्याओं को N से कम और से अधिक स्टोर कर सकते हैं 0

पिछली कक्षा का एराटोस्थनीज की छलनी एक प्राचीन और कुशल एल्गोरिथ्म है, जब N से कम के प्राइम्स मिलते हैं N, O को आवंटित करने के लिए छोटा है (N) मेमोरी में जगह। यह सभी गैर-अभाज्य संख्याओं को समग्र रूप से चिह्नित करके इसे समाप्त करता है। सभी कंपोजिट के चिह्नित होने के बाद, जो नंबर अनमार्क किए गए हैं, वे प्रिम्स हैं।

इसके अलावा, हमें एक बूलियन स्टोर करने की आवश्यकता है सरणी यह जांचने के लिए कि कोई संख्या चिह्नित है या नहीं, जो मेमोरी उपयोग के लिए है। तो, यह एक ऐसा मामला है जहां हम व्यापार स्मृति से दूर समय पर सुधार.

गिनती की शर्तें Leetcode Solutions

कलन विधि

  1. एक बूलियन सरणी बनाए रखें मुख्य के बराबर आकार एन - 1
  2. प्रधान[] का उपयोग कंपोजिट को चिन्हित करने और अंत में प्राइम चेक करने के लिए किया जाता है
  3. के रूप में हर पूर्णांक के प्रारंभिक प्रधानमंत्री <strong>उद्देश्य</strong>। एल्गोरिथ्म सेट करता है असत्य प्रत्येक गैर-अभाज्य संख्या में
  4. लगातार पूर्णांक के एक लूप को चलाएं, 2 से शुरू होकर पूर्णांक का पहला गुणक है एन से कम:
    • प्रत्येक पूर्णांक x के लिए, यदि इसमें प्राइम [x] सत्य है, तो इसके सभी गुणकों को चिह्नित करें असत्य
    • यहाँ पर हर पूर्णांक का गुणज शुरू होता है एक्स * एक्स एक्स के अन्य सभी गुणकों के रूप में पहले से ही चिह्नित किया जाएगा।
  5. अंत में जांचें कि [2, N - 1] रेंज में कितने नंबर हैं <strong>उद्देश्य</strong> प्राइम टेबल में
  6. परिणाम प्रिंट करें

गणना की शर्तों Leetcode समाधान का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int sieve(int N)
{
    if(N < 3)
        return 0;

    int cnt = 0;
    bool prime[N];
    for(int i = 2 ; i < N ; i++)
        prime[i] = true;

    for(int i = 2 ; i * i < N ; i++)
    {
        if(prime[i])
            for(int j = i * i ; j < N ; j += i)
                prime[j] = false;
    }

    for(int i = 2 ; i < N ; i++)
        if(prime[i])
            cnt++;

    return cnt;
}

int countPrimes(int N)
{
    if(N < 3)
        return 0;
    return sieve(N);
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

जावा प्रोग्राम

class count_primes
{
    static int sieve(int N)
    {
        if(N < 3)
            return 0;

        int cnt = 0;
        boolean[] prime= new boolean[N];
        for(int i = 2 ; i < N ; i++)
            prime[i] = true;

        for(int i = 2 ; i * i < N ; i++)
        {
            if(prime[i])
                for(int j = i * i ; j < N ; j += i)
                    prime[j] = false;
        }

        for(int i = 2 ; i < N ; i++)
            if(prime[i])
                cnt++;

        return cnt;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        return sieve(N);
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

काउंट प्राइम्स Leetcode Solutions की जटिलता विश्लेषण

समय जटिलता

एल्गोरिथ्म की जटिलता है O (Nlog (logN))। इसे इस प्रकार सिद्ध किया जा सकता है:

प्रत्येक पूर्णांक, X के लिए, हम एक समय व्यतीत करते हैं एन / एक्स अपने सभी गुणकों को नष्ट करना।

तो, कुल खर्च किया गया समय है: N / 2 + N / 3 + N / 5 + N / 7 + ……

आम के रूप में लेना T (N) = N (1/2 + 1/3 + 1/5 + 1/7 +…)। श्रृंखला के योग (१/२ + १/३ + १/५ + १/… +…) को सिद्ध किया जा सकता है log (logN)।

इसलिए, T (N) = Nlog (logN)

अंतरिक्ष की जटिलता

पर), जैसा कि हम एक संख्या को प्राइम या नहीं करने के लिए स्टोर करने के लिए हैश टेबल बनाते हैं।