1.
Problem
2.
Solution
2.1.
Algorithm
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Count of Arrays of Size N that can be Formed Starting With K Such that Every Element is Divisible by the Next Element

GAZAL ARORA
0 upvote

## Problem

Given two positive integers K, and N, find the number of arrays of size N that can be formed, having K as the first element and every element except the last is divisible by the array's next element. Since the count can be huge, print the modulo 109 + 7.

Input: Two integers N and K.

Output: An integer.

For example

``````1.
Input: N = 3, K = 25
Output: 5
Explanation:
There are 5 valid arrays of size 3 starting with 25 and satisfying the given condition:
{25, 25, 25}
{25, 25, 5}
{25, 5, 5}
{25, 5, 1}
{25, 1, 1}.

2.
Input: N = 2, K = 4
Output: 9
Explanation:
There are 3 valid arrays of size 2 starting with 4 and satisfying the given condition:
{4, 4}
{4, 2}
{4, 1}

3.
Input: N = 4, K = 5
Output: 4``````

Recommended: Try to solve it yourself before moving on to the solution.

## Solution

Approach: The idea is to use Combinators.

As given, the first element of the array must be K, and therefore to satisfy the condition that every element is divisible by the next element, the next element should be one of the factors of the K. We will find all the powers of prime factors of K and try to place them in the array such that every element is divisible by the next element.

### Algorithm

1. Initialise a variable res to store the count of arrays formed.
2. Initialise res as 1.
3. Find all powers of prime factors of K, and then do the following for each prime factor p:
1. Let count be the number of times p occurs in the value K.
2. Therefore, the number of possible ways to keep one of the factors of is given by  (N + count - 1)Ccount.
3. Multiply res by the value (N + count - 1)Ccount.
4. Return result.
``````// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

int MOD = 1000000007;

// Function to find the value of x raised to the power y modulo MOD
long modPower(long x, long y)
{

// Stores the value of x^y
long r = 1, a = x;

// Iterate until y is positive
while (y > 0) {
if ((y & 1) == 1) {
r = (r * a) % MOD;
}

a = (a * a) % MOD;
y /= 2;
}

return r;

}

// Function to perform use Fermat's little theorem for Modular Multiplicative Inverse
long modInverse(long x)
{
return modPower(x, MOD - 2);
}

// Modular division x / y, find the modular multiplicative inverse of y and multiply by x
long modDivision(long p, long q)
{
return (p * modInverse(q)) % MOD;
}

// Function to find Binomial Coefficient C(n, k) in O(k) time
long C(long n, int k)
{
// Base Case
if (k > n) {
return 0;
}

long p = 1, q = 1;
for (int i = 1; i <= k; i++) {

// Update the value of p and q
q = (q * i) % MOD;
p = (p * (n - i + 1)) % MOD;
}

return modDivision(p, q);
}

// Function to find the count of arrays having K as the first element satisfying the given criteria
int countArrays(int N, int K)
{
// Stores the resultant count of arrays
long res = 1;

// Find the factorization of K
for (int p = 2; p <=  sqrt(K) ; p++) {
int count = 0;

while (K % p == 0) {
K /= p;
count++;
}
res = (res * C(N - 1 + count, count)) % MOD;

}
if(K > 1){
// N Be the last prime factor, for c = 1 -> C(N-1+1, 1) = N
res = (K *res) % MOD;
}

return res;
}

int main()

{
int N = 3, K = 5;
cout << countArrays(N, K);
return 0;
}``````

Input: N = 3, K = 25

Output:

``5``

Time Complexity: O(√n ).

Space Complexity: O(1)

Also see, Euclid GCD Algorithm

## FAQs

1. What is a prime number?
A prime number is a number greater than 1 and can be divided by 1 or itself only. For example, 2, 5, 7, 11, 13, 17, 19, 23, 29, etc, are the prime numbers.

2. What is a factor of a number?
In mathematics, a factor is a number or algebraic expression that divides another number or expression completely without leaving any remainder. For example, 2 and 3 are the factors of 6, whereas five are not because 2 and 3 divide 6 entirely, and 5 leaves a remainder of 1.

## Key Takeaways

In this article, we designed an algorithm for counting the number of the N-sized arrays that can be formed with K as the starting element such that every element is divisible by the next element.
We used the mathematical concept of combinators to find the next possible element in the array. The time complexity of the algorithm is O(√n ), whereas the space complexity is O(1).