Problem link: Minimum jumps to reach end via prime teleportation
My solution:
class Solution {
public int minJumps(int[] nums) {
int maxVal = 1000_000;
int[] spf = new int[maxVal + 1];
for (int i = 2; i <= maxVal; i++) {
if (spf[i] == 0) {
spf[i] = i;
for (long j = (long) i * i; j <= maxVal; j += i) {
if (spf[(int) j] == 0) {
spf[(int) j] = i;
}
}
}
}
int n = nums.length;
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();
for (int i = 0; i < n; i++) {
int temp = nums[i];
while (temp > 1) {
int p = spf[temp];
if (!hm.containsKey(p))
hm.put(p, new ArrayList<>());
hm.get(p).add(i);
while (temp % p == 0)
temp /= p;
}
}
Queue<Integer> q = new LinkedList<>();
boolean[] visitedPrime = new boolean[maxVal + 1];
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
q.add(0);
while (!q.isEmpty()) {
int u = q.poll(), c = dist[u];
if (u == n - 1)
return c;
if (u - 1 >= 0 && dist[u - 1] == -1) {
dist[u - 1] = c + 1;
q.add(u - 1);
}
if (u + 1 < n && dist[u + 1] == -1) {
dist[u + 1] = c + 1;
q.add(u + 1);
}
if (spf[nums[u]] == nums[u] && !visitedPrime[nums[u]]) {
visitedPrime[nums[u]] = true;
for (int idx : hm.getOrDefault(nums[u], new ArrayList<>()))
if (idx != u && dist[idx] == -1) {
dist[idx] = c + 1;
q.add(idx);
}
}
}
return -1;
}
}
First for loop itself is going to the order of 10^9, you don’t need to go to that order, for all prime numbers p <= 1000 , there will be edge from p to 2*p … until 1000000,if there no edge to an index means it’s a prime number . There are 168 prime less than 1000, that should avoid TLE. The problem boils down to finding prime numbers up to 10^6 , you don’t need store the edges in adjacency list, you can generate them on the fly.
Isn't sieve O(n log log n)? That makes the loop 5*10^7 at most. Should be good enough to pass.
It isn't about primes or something, my code fails because say in a dense graph where all numbers in list are equal there would be n**2 edges. That won't be sufficient to traverse through DFS or BFS.
Not sure if you are talking about my code or your code. But if you are talking about my code, for this case I use the
visitedPrimeflag array.I was talking about my code. You can not precompute which edges to connect s it would be O(n**2). Do it on the go and a BFS suffices. Just quit the loop when the node n-1 is visited. Here is CPP code
There is not much wrong with your solution, on Leetcode time limit is combined for all test cases but you calculating primes up to 1000000 even for small test cases
Yes, this must be it. When I am calculating prime for max value in the array, it's getting passed. I believe there are some test cases missing in the problem.