CODEWITHSUNDEEP
algorithmdynamic-programming
Emma Funkhouser
Emma Funkhouser

Reputation: 39

Count number of subsequences of A such that every element of the subsequence is divisible by its index (starts from 1)

B is a subsequence of A if and only if we can turn A to B by removing zero or more element(s).

A = [1,2,3,4]
B = [1,4] is a subsequence of A.(Just remove 2 and 4).
B = [4,1] is not a subsequence of A.

Count all subsequences of A that satisfy this condition : A[i]%i = 0

Note that i starts from 1 not 0.

Example :

Input : 
5
2 2 1 22 14
Output:
13

All of these 13 subsequences satisfy B[i]%i = 0 condition.

{2},{2,2},{2,22},{2,14},{2},{2,22},{2,14},{1},{1,22},{1,14},{22},{22,14},{14}

My attempt :

The only solution that I could came up with has O(n^2) complexity.

Upvotes: 1

Views: 1221

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

For every divisor d of A[i], where d is greater than 1 and at most i+1, A[i] can be the dth element of the number of subsequences already counted for d-1.

JavaScript code: 

function getDivisors(n, max){
  let m = 1;
  const left = [];
  const right = [];
  
  while (m*m <= n && m <= max){
    if (n % m == 0){
      left.push(m);
      
      const l = n / m;
      
      if (l != m && l <= max)
        right.push(l);
    }
      
    m += 1;
  }
  
  return right.concat(left.reverse());
}


function f(A){
  const dp = [1, ...new Array(A.length).fill(0)];
  
  let result = 0;
  
  for (let i=0; i<A.length; i++){
    for (d of getDivisors(A[i], i+1)){
      result += dp[d-1];
      dp[d] += dp[d-1];
    }
  }
  
  return result;
}


var A = [2, 2, 1, 22, 14];
console.log(JSON.stringify(A));
console.log(f(A));

Upvotes: 2

johnchen902
johnchen902

Reputation: 9601

Assuming the maximum element in A is C, the following is an algorithm with time complexity O(n * sqrt(C)):

  1. For every element x in A, find all divisors of x.
  2. For every i from 1 to n, find every j such that A[j] is a multiple of i, using the result of step 1.
  3. For every i from 1 to n and j such that A[j] is a multiple of i (using the result of step 2), find the number of B that has i elements and the last element is A[j] (dynamic programming).
def find_factors(x):
    """Returns all factors of x"""
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            yield i
            if i != x // i:
                yield x // i

def solve(a):
    """Returns the answer for a"""
    n = len(a)

    # b[i] contains every j such that a[j] is a multiple of i+1.
    b = [[] for i in range(n)]
    for i, x in enumerate(a):
        for factor in find_factors(x):
            if factor <= n:
                b[factor - 1].append(i)

    # There are dp[i][j] sub arrays of A of length (i+1) ending at b[i][j]
    dp = [[] for i in range(n)]
    dp[0] = [1] * n
    for i in range(1, n):
        k = x = 0
        for j in b[i]:
            while k < len(b[i - 1]) and b[i - 1][k] < j:
                x += dp[i - 1][k]
                k += 1
            dp[i].append(x)

    return sum(sum(dpi) for dpi in dp)

Upvotes: 2

Nir H.
Nir H.

Reputation: 550

I believe that for the general case we can't provably find an algorithm with complexity less than O(n^2).

First, an intuitive explanation:

Let's indicate the elements of the array by a1, a2, a3, ..., a_n.

If the element a1 appears in a subarray, it must be element no. 1.

If the element a2 appears in a subarray, it can be element no. 1 or 2.

If the element a3 appears in a subarray, it can be element no. 1, 2 or 3.

...

If the element a_n appears in a subarray, it can be element no. 1, 2, 3, ..., n.

So to take all the possibilities into account, we have to perform the following tests:

Check if a1 is divisible by 1 (trivial, of course)

Check if a2 is divisible by 1 or 2

Check if a3 is divisible by 1, 2 or 3

...

Check if a_n is divisible by 1, 2, 3, ..., n

All in all we have to perform 1+ 2 + 3 + ... + n = n(n - 1) / 2 tests, which gives a complexity of O(n^2).

Note that the above is somewhat inaccurate, because not all the tests are strictly necessary. For example, if a_i is divisible by 2 and 3 then it must be divisible by 6. Nevertheless, I think this gives a good intuition.

Now for a more formal argument:

Define an array like so:

a1 = 1

a2 = 1× 2

a3 = 1× 2 × 3

...

a_n = 1 × 2 × 3 × ... × n

By the definition, every subarray is valid.

Now let (m, p) be such that m <= n and p <= n and change a_mtoa_m / p`. We can now choose one of two paths:

  1. If we restrict p to be prime, then each tuple (m, p) represents a mandatory test, because the corresponding change in the value of a_m changes the number of valid subarrays. But that requires prime factorization of each number between 1 and n. By the known methods, I don't think we can get here a complexity less than O(n^2).

  2. If we omit the above restriction, then we clearly perform n(n - 1) / 2 tests, which gives a complexity of O(n^2).

Upvotes: 0

Related Questions