Skip to content

Latest commit

 

History

History
142 lines (117 loc) · 4.24 KB

_3233. Find the Count of Numbers Which Are Not Special.md

File metadata and controls

142 lines (117 loc) · 4.24 KB

3233. Find the Count of Numbers Which Are Not Special

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Completed during Weekly Contest 408 (q2)

Back to top

First completed : July 28, 2024

Last updated : July 28, 2024

Related Topics : Array, Math, Number Theory

Acceptance Rate : 26.75 %

Notes

    1   No
    2   No
    3   No
    4   1, 2        YES
    5   No
    6   1, 2, 3 No
    7   No
    8   1, 2, 4
    9   1, 3        YES
    Has to be a square of a prime? Yes

I realized that we're essentially trying to count the number of primes in the range of [ceil(sqrt(l)), floor(sqrt(r))] inclusive since the only values that will only have the factors 1 and a single other number are squares of primes. Otherwise, it will be two numbers multiplied plus the "1" case which would be 3 or more.

I initially made the mistake of thinking there was no potential way to continue opimizing my Python method so I tried Java out. This mislead me as it increased the test cases I was passing from 400600 up to the last ~20 test cases, so I thought this was the genuine reason. I realized afterwards however that I wasn't optimized for checking roots only up to $\sqrt{n}$ and was instead checking all potential prime factors of $n$.

Solutions

Java

m3233 q2.java

class Solution {
    public int nonSpecialCount(int l, int r) {
        int smallestVal = (int) Math.ceil(Math.sqrt(l));
        int largestVal = (int) Math.floor(Math.sqrt(r));
        int leftIndx = 0;

        // # 2 isn't prime but is needed in this list unfort
        ArrayList<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        primes.add(3);
        primes.add(5);

        int offset = 2;
        int lastInt = primes.get(primes.size() - 1);
        while (lastInt * lastInt <= r) {
            int nextPrime = lastInt + offset;
            boolean isPrime = true;
            for (int prime : primes) {
                if (prime * prime > nextPrime) {
                    break;
                }
                if (nextPrime % prime == 0) {
                    isPrime = false;
                    break;
                }
            }
            
            if (isPrime) {
                offset = 2;
                primes.add(nextPrime);
                lastInt = nextPrime;
            }
            else
                offset += 2;
        }

        double rooted = Math.sqrt((double) l);
        int firstRoot = (int) Math.ceil(rooted);
        int starterIndx = (firstRoot == 1) ? 0 : Collections.binarySearch(primes, firstRoot);

        if (starterIndx <= -1) {
            starterIndx = -1 - starterIndx;
        }

        while (!primes.isEmpty() && primes.get(primes.size() - 1) * primes.get(primes.size() - 1) > r) {
            primes.remove(primes.size() - 1);
        }
        
        return r - l + 1 - (primes.size() - starterIndx);
    }
}

Python

m3233 q2.py

class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        primes = [2, 3, 5]
        offset = 2
        while primes[-1] ** 2 <= r :
            nextPrime = primes[-1] + offset
            isPrime = True
            for prime in primes :
                if prime ** 2 > nextPrime :
                    break
                if nextPrime % prime == 0 :
                    isPrime = False
                    break

            if isPrime :
                offset = 2
                primes.append(nextPrime)
            else :
                offset += 2

        starterIndx = bisect_left(primes, ceil(sqrt(l)))

        while primes and primes[-1] ** 2 > r :
            primes.pop()

        return r - l + 1 - (len(primes) - starterIndx)