commit 51ee1efe0ccdeb1f7e1a5a2648ba4624d6e08a41
parent 151230d6514e16b2739c0f52ddf52b6fc96740ab
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 7 May 2026 21:25:44 -0600
3629. minimum jumps to reach end via prime teleportation
Diffstat:
2 files changed, 219 insertions(+), 0 deletions(-)
diff --git a/min_jumps_end_prime_tele.c b/min_jumps_end_prime_tele.c
@@ -0,0 +1,159 @@
+// 3629. Minimum Jumps to Reach End via Prime Teleportation
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' of length 'n'. you start at index 0,
+ * and your goal is to reach index 'n - 1'. from any index 'i', you may perform
+ * onee of the following operations: adjacent step: jump to index 'i + 1' or 'i
+ * - 1', if the index is within bounds, or prime teleportation: if 'nums[i]' is
+ * a prime number, you may instantly jump to any index 'j != i' such that
+ * 'nums[j] % p == 0'. return the minimum number of jumps to reach the index 'n
+ * - 1'.
+ */
+
+#define MAX_SIZE 1000001
+#define HASH_SIZE 10007
+
+typedef struct {
+ int *data;
+ int size;
+ int cap;
+} vector;
+
+typedef struct node {
+ int key;
+ vector values;
+ struct node *next;
+} node;
+
+static node *hash_table[HASH_SIZE];
+static vector factors[MAX_SIZE];
+static bool precomputed = false;
+
+void vector_push(vector *v, int val) {
+ if (v->size == v->cap) {
+ v->cap = v->cap == 0 ? 2 : v->cap * 2;
+ v->data = (int *)realloc(v->data, v->cap * sizeof(int));
+ }
+ v->data[v->size++] = val;
+}
+
+void hash_push(int key, int val) {
+ int h = abs(key) % HASH_SIZE;
+ node *cur = hash_table[h];
+ while (cur) {
+ if (cur->key == key) {
+ vector_push(&cur->values, val);
+ return;
+ }
+ cur = cur->next;
+ }
+ node *new_node = (node *)malloc(sizeof(node));
+ new_node->key = key;
+ memset(&new_node->values, 0, sizeof(vector));
+ vector_push(&new_node->values, val);
+ new_node->next = hash_table[h];
+ hash_table[h] = new_node;
+}
+
+vector *hash_get(int key) {
+ int h = abs(key) % HASH_SIZE;
+ node *cur = hash_table[h];
+ while (cur) {
+ if (cur->key == key)
+ return &cur->values;
+ cur = cur->next;
+ }
+ return NULL;
+}
+
+void precompute() {
+ if (precomputed)
+ return;
+ for (int i = 2; i < MAX_SIZE; i++) {
+ if (factors[i].size == 0) {
+ for (int j = i; j < MAX_SIZE; j += i) {
+ vector_push(&factors[j], i);
+ }
+ }
+ }
+ precomputed = true;
+}
+
+void clear_hash() {
+ for (int i = 0; i < HASH_SIZE; i++) {
+ node *cur = hash_table[i];
+ while (cur) {
+ node *tmp = cur;
+ cur = cur->next;
+ free(tmp->values.data);
+ free(tmp);
+ }
+ hash_table[i] = NULL;
+ }
+}
+
+int minJumps(int *nums, int numsSize) {
+ precompute();
+ clear_hash();
+ int n = numsSize;
+ for (int i = 0; i < n; i++)
+ for (int p_idx = 0; p_idx < factors[nums[i]].size; p_idx++)
+ hash_push(factors[nums[i]].data[p_idx], i);
+ bool *vis = (bool *)calloc(n, sizeof(bool));
+ int *q = (int *)malloc(n * sizeof(int));
+ int q_start = 0, q_end = 0;
+ vis[0] = true;
+ q[q_end++] = 0;
+ int ans = 0;
+ while (q_start < q_end) {
+ int level_size = q_end - q_start;
+ for (int k = 0; k < level_size; k++) {
+ int i = q[q_start++];
+ if (i == n - 1) {
+ free(vis);
+ free(q);
+ return ans;
+ }
+ if (i > 0 && !vis[i - 1]) {
+ vis[i - 1] = true;
+ q[q_end++] = i - 1;
+ }
+ if (i < n - 1 && !vis[i + 1]) {
+ vis[i + 1] = true;
+ q[q_end++] = i + 1;
+ }
+ if (factors[nums[i]].size == 1) {
+ int p = nums[i];
+ vector *v = hash_get(p);
+ if (v) {
+ for (int j_idx = 0; j_idx < v->size; j_idx++) {
+ int j = v->data[j_idx];
+ if (!vis[j]) {
+ vis[j] = true;
+ q[q_end++] = j;
+ }
+ }
+ v->size = 0;
+ }
+ }
+ }
+ ans++;
+ }
+ return -1;
+}
+
+int main() {
+ int n1[] = {1, 2, 4, 6};
+ int n2[] = {2, 3, 4, 7, 9};
+ int n3[] = {4, 6, 5, 8};
+ int r1 = minJumps(n1, ARRAY_SIZE(n1));
+ int r2 = minJumps(n2, ARRAY_SIZE(n2));
+ int r3 = minJumps(n3, ARRAY_SIZE(n3));
+ printf("%d\n", r1);
+ assert(r1 == 2);
+ printf("%d\n", r2);
+ assert(r2 == 2);
+ printf("%d\n", r3);
+ assert(r3 == 3);
+}
diff --git a/min_jumps_end_prime_tele.py b/min_jumps_end_prime_tele.py
@@ -0,0 +1,60 @@
+# 3629. Minimum Jumps to Reach End via Prime Teleportation
+from collections import defaultdict
+from typing import List
+
+"""
+you are given an integer array 'nums' of length 'n'. you start at index 0,
+and your goal is to reach index 'n - 1'. from any index 'i', you may perform
+onee of the following operations: adjacent step: jump to index 'i + 1' or 'i
+- 1', if the index is within bounds, or prime teleportation: if 'nums[i]' is
+a prime number, you may instantly jump to any index 'j != i' such that
+'nums[j] % p == 0'. return the minimum number of jumps to reach the index 'n
+- 1'.
+"""
+
+MX = 1_000_001
+factors = [[] for _ in range(MX)]
+for i in range(2, MX):
+ if not factors[i]:
+ for j in range(i, MX, i):
+ factors[j].append(i)
+
+
+class Solution:
+ def minJumps(self, nums: List[int]) -> int:
+ n = len(nums)
+ edges = defaultdict(list)
+ for i, a in enumerate(nums):
+ for p in factors[a]:
+ edges[p].append(i)
+ ans = 0
+ vis = [False] * n
+ vis[0] = True
+ q = [0]
+ while True:
+ q2 = []
+ for i in q:
+ if i == n - 1:
+ return ans
+ if i > 0 and not vis[i - 1]:
+ vis[i - 1] = True
+ q2.append(i - 1)
+ if i < n - 1 and not vis[i + 1]:
+ vis[i + 1] = True
+ q2.append(i + 1)
+ if len(factors[nums[i]]) == 1:
+ p = nums[i]
+ for j in edges[p]:
+ if not vis[j]:
+ vis[j] = True
+ q2.append(j)
+ edges[p].clear()
+ q = q2
+ ans += 1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minJumps(nums=[1, 2, 4, 6]))
+ print(obj.minJumps(nums=[2, 3, 4, 7, 9]))
+ print(obj.minJumps(nums=[4, 6, 5, 8]))
