Shortest Path via Divisibility — Problem Statement & Solution Guide

GraphsMediumMixed

TimeO(n * (sqrt(C) + C / minValue)) ≈ O(n log C)

SpaceO(n + C)

Problem Description

You are given an integer array nums and two integers start and end, representing 0-indexed positions in nums.

You can move from index i to index j (i != j) if and only if nums[i] is a multiple of nums[j], or nums[j] is a multiple of nums[i].

Return the minimum number of moves to travel from index start to index end. If there is no possible path, return -1.

DSA Pattern Breakdown

"Shortest Path via Divisibility"

medium

WHY DOES IT MATTER?

Divisibility graphs appear in many number‑theoretic and scheduling problems where resources can be combined or split based on factor relationships. Recognizing the underlying graph and applying BFS avoids brute‑force pair checks, turning an exponential‑looking search into a linear‑ish algorithm.

OPTIMIZATION CHALLENGE

The key insight is to pre‑bucket indices by their numeric value and generate neighbours lazily via divisor and multiple enumeration, marking each bucket visited only once. This eliminates the O(n²) pairwise checks and reduces the problem to scanning each value’s divisor set (≈√v) and its multiple multiples (≈C/v), yielding near‑linear total work.

REAL-WORLD CONNECTION

Think of a distributed cache where each node stores data blocks of size v. A node can directly replicate data to another node if the block size is a multiple of the other's capacity. Finding the fewest replication hops mirrors the shortest‑path via divisibility, and the bucket‑by‑size technique mirrors how systems index nodes by capacity for fast lookup.

During an interview, first state the graph model, then immediately discuss why building the full adjacency matrix is a dead end. Jump to the bucket‑by‑value trick, explain divisor generation and multiple stepping, and emphasize marking value‑buckets as visited to guarantee O(n · log C) runtime.

COMPLEXITY AT A GLANCE

⏱ Time:O(n * (sqrt(C) + C / minValue)) ≈ O(n log C)

💾 Space:O(n + C)

Core Theory — Why This Approach?

The problem can be modeled as an unweighted undirected graph where each array index is a vertex and an edge exists between i and j if nums[i] and nums[j] satisfy a divisibility relation (one is a multiple of the other). The shortest‑path question therefore reduces to a BFS traversal from the start vertex to the end vertex. A naïve construction of the graph examines every pair of indices, yielding O(n²) time and memory – infeasible for n in the order of 10⁵. The optimal paradigm leverages the arithmetic structure of divisibility: instead of enumerating all pairs, we index the positions of each distinct value and generate neighbours on‑the‑fly by enumerating a number’s divisors (via prime factorisation) and its multiples up to the global maximum. This transforms the edge‑generation step into a near‑linear process, allowing BFS to run in O(n · log C) time where C = max(nums). The space usage drops to O(n + C) for the value‑to‑indices buckets and the BFS queue.

In practice, each value v contributes two families of neighbours: (1) all indices whose values are divisors of v – obtained by enumerating every divisor d of v in O(√v) time, and (2) all indices whose values are multiples of v – obtained by stepping through k·v for k = 2,3,… up to C and consulting a pre‑built bucket of indices for each multiple. By marking values as “visited” after their first expansion we avoid re‑processing the same divisor/multiple set, guaranteeing that each bucket is scanned at most once. This insight collapses the quadratic blow‑up into a manageable linear‑ish workload suitable for interview constraints.

The BFS guarantees the minimal number of moves because every edge has equal weight. If the end index is never dequeued, the graph is disconnected and the answer is –1. This combination of number‑theoretic preprocessing and classic graph traversal is a textbook example of turning a combinatorial explosion into a tractable search.

Interview Questions on This Problem

Q1How would you modify the solution if the move condition required nums[i] to be a proper divisor of nums[j] (i.e., nums[i] < nums[j] and nums[j] % nums[i] == 0)?

You would keep the same BFS framework but restrict neighbour generation to only the ‘multiple’ direction. When expanding a node with value v, you only consider indices whose values are strict multiples of v (k·v for k≥2). Divisor‑to‑multiple edges become directed, so you no longer need to generate divisor neighbours, which simplifies the preprocessing and reduces the number of visited buckets.

Q2What is the time complexity if all numbers in nums are prime and distinct?

When all numbers are distinct primes, each number has exactly two divisibility relations: it is only divisible by 1 (which is absent) and it divides no other number. Hence the adjacency list for each vertex is empty, and BFS terminates immediately. The preprocessing still scans each value to build buckets, so the overall time is O(n) plus the O(√v) divisor enumeration which yields O(n · √P) where P is the maximum prime, but practically it behaves linear because divisor generation quickly returns only the number itself.

Q3Can you solve the problem using a Union‑Find (Disjoint Set) data structure instead of BFS? Why or why not?

Union‑Find can identify connectivity components in O(α(n)) per union, but it cannot provide the shortest‑path length because it loses distance information. While you could use it to quickly answer whether a path exists, the problem explicitly asks for the minimum number of moves, which requires a level‑by‑level exploration that BFS naturally provides.

Examples

Example 1

Input

[6, 2, 8, 6, 2, 8], 0, 2

Output

Explanation: Step-by-step: We can move from index 0 to index 3 because 6 is a multiple of 6, and then from index 3 to index 2 because 6 is a multiple of 8, so the minimum number of moves is 2.

Example 2

Input

[2, 6, 2, 2, 6, 8], 0, 5

Output

Explanation: Step-by-step: We can move from index 0 to index 1 because 2 is a multiple of 6, and then from index 1 to index 4 because 2 is a multiple of 2, and then from index 4 to index 5 because 2 is a multiple of 8, so the minimum number of moves is 3.

Constraints

2 <= nums.length <= 1000
1 <= nums[i] <= 10^6
0 <= start, end < nums.length

Optimal Approach & Strategy

Bucket indices by value, generate neighbours on‑the‑fly via divisor enumeration and multiple stepping, and perform BFS while marking value buckets as visited.

Brute Force Approach

Check every pair of indices to build all possible edges, then run BFS on the resulting O(n²) graph.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n * (sqrt(C) + C / minValue)) ≈ O(n log C)

function solution(nums, start, end) {
   const n = nums.length;
   const visited = new Array(n).fill(false);
   const queue = [[start, 0]];
   visited[start] = true;
   while (queue.length > 0) {
       const [node, step] = queue.shift();
       if (node === end) return step;
       for (let i = 0; i < n; i++) {
           if (!visited[i] && nums[node] % nums[i] === 0 || nums[i] % nums[node] === 0) {
               queue.push([i, step + 1]);
               visited[i] = true;
           }
       }
   }
   return -1;
}

class Solution {
   public:
       int solution(vector<int>& nums, int start, int end) {
           int n = nums.size();
           vector<bool> visited(n, false);
           queue<int[]> q;
           q.push({start, 0});
           visited[start] = true;
           while (!q.empty()) {
               int* node = q.front();
               q.pop();
               if (node[0] == end) return node[1];
               for (int i = 0; i < n; i++) {
                   if (!visited[i] && nums[node[0]] % nums[i] == 0 || nums[i] % nums[node[0]] == 0) {
                       q.push({i, node[1] + 1});
                       visited[i] = true;
                   }
               }
           }
           return -1;
       }
   };

class Solution {
   public int solution(int[] nums, int start, int end) {
       int n = nums.length;
       boolean[] visited = new boolean[n];
       Queue<int[]> queue = new LinkedList<>();
       queue.offer(new int[] {start, 0});
       visited[start] = true;
       while (!queue.isEmpty()) {
           int[] node = queue.poll();
           if (node[0] == end) return node[1];
           for (int i = 0; i < n; i++) {
               if (!visited[i] && nums[node[0]] % nums[i] == 0 || nums[i] % nums[node[0]] == 0) {
                   queue.offer(new int[] {i, node[1] + 1});
                   visited[i] = true;
               }
           }
       }
       return -1;
   }
}

def solution(nums, start, end):
   n = len(nums)
   visited = [False] * n
   queue = [[start, 0]]
   visited[start] = True
   while queue:
       node, step = queue.pop(0)
       if node == end: return step
       for i in range(n):
           if not visited[i] and nums[node] % nums[i] == 0 or nums[i] % nums[node] == 0:
               queue.append([i, step + 1])
               visited[i] = True
   return -1

function solution(nums, start, end) {
   const n = nums.length;
   const visited = new Array(n).fill(false);
   const queue = [[start, 0]];
   visited[start] = true;
   while (queue.length > 0) {
       const [node, step] = queue.shift();
       if (node === end) return step;
       for (let i = 0; i < n; i++) {
           if (!visited[i] && nums[node] % nums[i] === 0 || nums[i] % nums[node] === 0) {
               queue.push([i, step + 1]);
               visited[i] = true;
           }
       }
   }
   return -1;
}

Asked in Top Tech Interviews

uncategorizedmediumnone

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Shortest Path via Divisibility Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Shortest Path via Divisibility — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor