Sequences where Adjacent Divide

Time: O(n*m^2)

Space: O(n*m)

Problem Overview

Count sequences of length n with each value in 1..m such that every adjacent pair has one dividing the other.

Intuition

Count sequences of length n with each value in 1..m such that every adjacent pair has one dividing the other. Build position by position: the state is how many slots are filled and what the previous value was. From a previous value, every compatible next choice extends a valid prefix; from sentinel 0 any first value is allowed.

Algorithm

1Memoize solve(len, last): number of ways to finish a sequence after placing len elements ending with last.
2Base: if len == n return 1 (one completed sequence).
3Otherwise try each i in 1..m; accept if last == 0 or i % last == 0 or last % i == 0.
4Sum recursive results and store in dp[len][last]. Call solve(0, 0) for the full answer.

Example Walkthrough

Input: n = 3, m = 2

1. Valid pairs among {1,2}: (1,1), (1,2), (2,1), (2,2) - all adjacent pairs divide.
2. Every length-3 sequence over {1,2} works: 2^3 = 8.
3. DP reaches the same count by extending prefixes under the divisibility rule.

Output: 8

Common Pitfalls

• Use last = 0 only as a start sentinel - it is not a real array value.
• Initialize the memo table to -1 so 0 ways are distinguishable from uncomputed.
• Check both directions: i divides last or last divides i.
• Naive m^n search without memo times out; state space is O(n*m) with O(m) work each.

Sequences where Adjacent Divide.java

Java

// Approach: Count length-n sequences with values in 1..m where each adjacent
// pair (a, b) satisfies a divides b or b divides a. Memoize on (filled length,
// last value); from last, try every next i that is compatible (or any i if last
// is the sentinel 0). A sequence is valid once filled length reaches n.
// Time: O(n*m^2) Space: O(n*m)
class Solution {

    private int solve(int n, int m, int len, int last, int[][] dp) {
        if (len == n) {
            return 1;
        }

        if (dp[len][last] != -1) {
            return dp[len][last];
        }

        int ans = 0;
        for (int i = 1; i <= m; i++) {
            if (last == 0 || i % last == 0 || last % i == 0) {
                ans += solve(n, m, len + 1, i, dp);
            }
        }

        return dp[len][last] = ans;
    }

    public int count(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = -1;
            }
        }
        return solve(n, m, 0, 0, dp);
    }
}

Was this solution helpful?