ಎಣಿಕೆ ಅವಿಭಾಜ್ಯಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ ಕ್ಯಾಪಿಟಲ್ ಒನ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಹ್ಯಾಶಿಂಗ್ ಮಠ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಒಂದು ಪೂರ್ಣಾಂಕವನ್ನು ನೀಡಲಾಗಿದೆ. N ಗಿಂತ ಕಡಿಮೆ ಸಂಖ್ಯೆಗಳು ಅವಿಭಾಜ್ಯಗಳಾಗಿವೆ ಎಂಬುದನ್ನು ಎಣಿಸುವುದು ಗುರಿಯಾಗಿದೆ. ಪೂರ್ಣಾಂಕವು .ಣಾತ್ಮಕವಲ್ಲ ಎಂದು ನಿರ್ಬಂಧಿಸಲಾಗಿದೆ.

ಉದಾಹರಣೆ

7
3
10
4

ವಿವರಣೆ

10 ಕ್ಕಿಂತ ಕಡಿಮೆ ಅವಿಭಾಜ್ಯಗಳು 2, 3, 5 ಮತ್ತು 7. ಆದ್ದರಿಂದ, ಎಣಿಕೆ 4 ಆಗಿದೆ.

ಅಪ್ರೋಚ್ (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

N ಗಿಂತ ಕಡಿಮೆ ಇರುವ ಪ್ರತಿ ಪೂರ್ಣಾಂಕವನ್ನು ಪರಿಶೀಲಿಸುವುದು ಮತ್ತು ಅವು ಅವಿಭಾಜ್ಯವಾಗಿದ್ದರೆ ಫಲಿತಾಂಶವನ್ನು ಹೆಚ್ಚಿಸುವುದು ಸಾಮಾನ್ಯ ವಿಧಾನವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, N = 10 ಅನ್ನು ಪರಿಗಣಿಸಿ. ಈಗ, ಈ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಎಷ್ಟು ಅವಿಭಾಜ್ಯಗಳಿವೆ ಎಂಬುದನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು 2 ರಿಂದ N - 1 ರವರೆಗೆ ಚೆಕ್ ಅನ್ನು ಚಲಾಯಿಸಬಹುದು. ಆದರೆ, ಈ ವಿಧಾನಕ್ಕೆ ಇಡೀ ಶ್ರೇಣಿಯಲ್ಲಿ ಅವಿಭಾಜ್ಯ ಪರಿಶೀಲನೆ ಅಗತ್ಯವಿದೆ, [2, ಎನ್ - 1].  ಆದ್ದರಿಂದ, ಇದು ನಿಧಾನವಾಗಿರುತ್ತದೆ.

ನಾವು ಕೆಲವು ಆಪ್ಟಿಮೈಸೇಶನ್ಗಳನ್ನು ಮಾಡಬಹುದು:

  1. 2 ಹೊರತುಪಡಿಸಿ ಪ್ರತಿಯೊಂದು ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆಯು ಬೆಸ ಪೂರ್ಣಾಂಕವಾಗಿದೆ. ಆದ್ದರಿಂದ, ನಂತರ 2, ನಾವು ಬೆಸ ಪೂರ್ಣಾಂಕಗಳಿಗಾಗಿ ಮಾತ್ರ ಪರಿಶೀಲಿಸಬಹುದು.
  2. ಒಂದು ಸಂಖ್ಯೆ ಅವಿಭಾಜ್ಯವಾಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬಹುದು ಒ () N) ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸುಧಾರಿಸುವ ಸಮಯ.

ಹೇಗಾದರೂ, ನಾವು ಇನ್ನೂ ಉತ್ತಮ ವಿಧಾನವನ್ನು ಹೊಂದಿದ್ದೇವೆ, ನಂತರ ಈ ಲೇಖನದಲ್ಲಿ ಚರ್ಚಿಸಲಾಗಿದೆ.

ಕ್ರಮಾವಳಿ

  1. ಸಂಖ್ಯೆ ಕಡಿಮೆ ಇದ್ದರೆ 3, ಹಿಂತಿರುಗಿ 0, 2 ಚಿಕ್ಕ ಅವಿಭಾಜ್ಯವಾಗಿದೆ
  2. 3 ರಿಂದ ಪ್ರಾರಂಭಿಸಿ ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳನ್ನು ಪರಿಶೀಲಿಸುವ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ
  3. ಒಂದು ಸಂಖ್ಯೆ, N ಅವಿಭಾಜ್ಯವಾಗಿದ್ದರೆ:
    • ಇದು ಹೊಂದಿದೆ 2 ಮತ್ತು ನಡುವಿನ ಅವಿಭಾಜ್ಯ ಅಂಶಗಳು √N
  4. ಸಂಖ್ಯೆ ಅವಿಭಾಜ್ಯವಾಗಿದ್ದರೆ, ಏರಿಕೆ ಫಲಿತಾಂಶ
  5. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಕೌಂಟ್ ಪ್ರೈಮ್‌ಗಳ ಅನುಷ್ಠಾನ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳು

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಕೌಂಟ್ ಪ್ರೈಮ್‌ಗಳ ಸಂಕೀರ್ಣ ವಿಶ್ಲೇಷಣೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳು

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಇದಕ್ಕಾಗಿ ನಾವು ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸುತ್ತೇವೆ ಎನ್ / 2 ಬಾರಿ. ಪ್ರತಿ ಚೆಕ್‌ನಲ್ಲಿ, ಒ (ಎನ್ / 2) ಸಂಕೀರ್ಣತೆಯ ಸಮಯ (ಸರಾಸರಿ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎನ್ / 2) ಖರ್ಚು ಮಾಡಲಾಗಿದೆ. ಆದ್ದರಿಂದ, ಈ ಅಲ್ಗಾರಿದಮ್ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ O (N√N).

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಸ್ಥಿರ ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ಬಳಸಲಾಗುತ್ತದೆ.

ಅಪ್ರೋಚ್ (ಆಪ್ಟಿಮಲ್ ವಿಧಾನ)

ಯಾವುದೇ ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ, ಹೇಳೋಣ 5, ನಂತರ 5 ರ ಎಲ್ಲಾ ಗುಣಾಕಾರಗಳು ಸ್ವತಃ ಹೊರತುಪಡಿಸಿ ಅವಿಭಾಜ್ಯವಾಗಲು ಸಾಧ್ಯವಿಲ್ಲ, ಏಕೆಂದರೆ ಅವುಗಳು 5 ಅನ್ನು ತಮ್ಮ ಅವಿಭಾಜ್ಯ ಅಂಶಗಳಲ್ಲಿ ಒಂದಾಗಿ ಹೊಂದಿರುತ್ತವೆ. ಅಂತೆಯೇ, ನಾವು ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳನ್ನು N ಗಿಂತ ಕಡಿಮೆ ಮತ್ತು ಅದಕ್ಕಿಂತ ಹೆಚ್ಚಿನದನ್ನು ಸಂಗ್ರಹಿಸಬಹುದು 0

ದಿ ಎರಾಟೋಸ್ಥೆನಿಸ್ ಜರಡಿ N ಗಿಂತ ಕಡಿಮೆ ಅವಿಭಾಜ್ಯಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪ್ರಾಚೀನ ಮತ್ತು ಪರಿಣಾಮಕಾರಿ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ O (N) ಅನ್ನು ನಿಯೋಜಿಸಲು N ಚಿಕ್ಕದಾಗಿದೆ ಮೆಮೊರಿಯಲ್ಲಿ ಸ್ಥಳ. ಇದು ಅವಿಭಾಜ್ಯೇತರ ಸಂಖ್ಯೆಗಳನ್ನು ಸಂಯೋಜಿತ ಎಂದು ಗುರುತಿಸುವ ಮೂಲಕ ಪುನರಾವರ್ತಿಸುತ್ತದೆ. ಎಲ್ಲಾ ಸಂಯೋಜನೆಗಳನ್ನು ಗುರುತಿಸಿದ ನಂತರ, ಗುರುತು ಹಾಕದ ಸಂಖ್ಯೆಗಳು ಅವಿಭಾಜ್ಯಗಳಾಗಿವೆ.

ಅಲ್ಲದೆ, ನಾವು ಬೂಲಿಯನ್ ಅನ್ನು ಸಂಗ್ರಹಿಸಬೇಕಾಗಿದೆ ಸರಣಿ ಯಾವುದೇ ಸಂಖ್ಯೆಯನ್ನು ಗುರುತಿಸಲಾಗಿದೆಯೆ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಲು, ಇದು ಮೆಮೊರಿ ಬಳಕೆಗೆ ಕಾರಣವಾಗಿದೆ. ಆದ್ದರಿಂದ, ಇದು ನಾವು ಇರುವ ಸಂದರ್ಭವಾಗಿದೆ ವ್ಯಾಪಾರ ಮೆಮೊರಿ ಆಫ್ ಸಮಯಕ್ಕೆ ಸುಧಾರಿಸಿ.

ಎಣಿಕೆ ಅವಿಭಾಜ್ಯಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳು

ಕ್ರಮಾವಳಿ

  1. ಬೂಲಿಯನ್ ರಚನೆಯನ್ನು ನಿರ್ವಹಿಸಿ ಪ್ರಧಾನ ಗಾತ್ರಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತದೆ ಎನ್ - 1
  2. ಅವಿಭಾಜ್ಯ [] ಸಂಯೋಜನೆಗಳನ್ನು ಗುರುತಿಸಲು ಮತ್ತು ಕೊನೆಯಲ್ಲಿ ಅವಿಭಾಜ್ಯಗಳನ್ನು ಪರಿಶೀಲಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ
  3. ಪ್ರತಿ ಪೂರ್ಣಾಂಕದ ಅವಿಭಾಜ್ಯವನ್ನು ಪ್ರಾರಂಭಿಸಿ ನಿಜವಾದ. ಅಲ್ಗಾರಿದಮ್ ಹೊಂದಿಸುತ್ತದೆ ಸುಳ್ಳು ಪ್ರತಿ ಅವಿಭಾಜ್ಯವಲ್ಲದ ಸಂಖ್ಯೆಗೆ
  4. 2 ರಿಂದ ಪ್ರಾರಂಭಿಸಿ ಪೂರ್ಣಾಂಕದ ಮೊದಲ ಗುಣಾಕಾರದವರೆಗೆ ಸತತ ಪೂರ್ಣಾಂಕಗಳ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ N ಗಿಂತ ಕಡಿಮೆ:
    • ಪ್ರತಿ ಪೂರ್ಣಾಂಕ x ಗೆ, ಅದು ಅವಿಭಾಜ್ಯ [x] ಅನ್ನು ನಿಜವೆಂದು ಹೊಂದಿದ್ದರೆ, ಅದರ ಎಲ್ಲಾ ಬಹುಸಂಖ್ಯೆಯನ್ನು ಹೀಗೆ ಗುರುತಿಸಿ ಸುಳ್ಳು
    • ಇಲ್ಲಿರುವ ಪ್ರತಿ ಪೂರ್ಣಾಂಕದ ಬಹುಸಂಖ್ಯೆಯು ಪ್ರಾರಂಭವಾಗುತ್ತದೆ x * x x ನ ಎಲ್ಲಾ ಇತರ ಗುಣಾಕಾರಗಳನ್ನು ಈಗಾಗಲೇ ಗುರುತಿಸಲಾಗಿಲ್ಲ.
  5. [2, N - 1] ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಎಷ್ಟು ಸಂಖ್ಯೆಗಳಿವೆ ಎಂದು ಅಂತಿಮವಾಗಿ ಪರಿಶೀಲಿಸಿ ನಿಜವಾದ ಅವಿಭಾಜ್ಯ ಕೋಷ್ಟಕದಲ್ಲಿ
  6. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಕೌಂಟ್ ಪ್ರೈಮ್‌ಗಳ ಅನುಷ್ಠಾನ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳು

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಕೌಂಟ್ ಪ್ರೈಮ್‌ಗಳ ಸಂಕೀರ್ಣ ವಿಶ್ಲೇಷಣೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಗಳು

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಅಲ್ಗಾರಿದಮ್ನ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ O (Nlog (logN)). ಇದನ್ನು ಹೀಗೆ ಸಾಬೀತುಪಡಿಸಬಹುದು:

ಪ್ರತಿ ಪೂರ್ಣಾಂಕ, ಎಕ್ಸ್, ನಾವು ಸಮಯವನ್ನು ಕಳೆಯುತ್ತೇವೆ ಎನ್ / ಎಕ್ಸ್ ಅದರ ಎಲ್ಲಾ ಗುಣಾಕಾರಗಳನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ.

ಆದ್ದರಿಂದ, ಒಟ್ಟು ಖರ್ಚು ಮಾಡಿದ ಸಮಯ: N / 2 + N / 3 + N / 5 + N / 7 + ……

ಎನ್ ಅನ್ನು ಸಾಮಾನ್ಯವೆಂದು ತೆಗೆದುಕೊಳ್ಳುವುದು, ಟಿ (ಎನ್) = ಎನ್ (1/2 + 1/3 + 1/5 + 1/7 +…). ಸರಣಿಯ ಮೊತ್ತವನ್ನು (1/2 + 1/3 + 1/5 + 1/7 +…) ಎಂದು ಸಾಬೀತುಪಡಿಸಬಹುದು ಲಾಗ್ (ಲಾಗ್ಎನ್).

ಆದ್ದರಿಂದ, ಟಿ (ಎನ್) = ಎನ್ಲಾಗ್ (ಲಾಗ್ ಎನ್)

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಒಂದು ಸಂಖ್ಯೆ ಅವಿಭಾಜ್ಯವಾಗಿದೆಯೋ ಇಲ್ಲವೋ ಎಂದು ಸಂಗ್ರಹಿಸಲು ನಾವು ಹ್ಯಾಶ್ ಟೇಬಲ್ ಅನ್ನು ರಚಿಸುತ್ತೇವೆ.