CODEWITHSUNDEEP
algorithmdynamic-programming
matt danny
matt danny

Reputation: 13

number of possible arrays with certain conditions using dp

an array of increasing natural numbers between 1 and n is called beautiful if each number in the array is divisible by it's previous number. using dynamic programming, the question is to find the number of beautiful arrays with size k with the given time complexity:

  1. O(n*k*root(n))
  2. O(n*k*log(n))

what I could think of for the first one is that the number of divisors of a number can be found with O(root(n)) time complexity. I want to design a recursive algorithm that calculates the number of possible arrays for each i < k but I can't figure out how.

Upvotes: 1

Views: 134

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

This problem can be broken into two parts:

  1. Find the divisor DAG (nodes 1…n, arcs a → b iff a divides b). Trial division will do this in Θ(n √n); enumerating multiples, in Θ(n log n). The graph has Θ(n log n) arcs.

  2. Count the number of paths of length k in a DAG. This is a basic Θ((m + n) k)-time dynamic program. There is one path of length 0 from each node. The number of paths of length ℓ from each node is the sum of the number of paths of length ℓ−1 from its successors.

Upvotes: 2

Related Questions