Scribd
Upload
104 views3 pages

Coding Exercise 1

The function dfcount takes integers n and k as parameters. It returns the number of arrays of length n where each element is between 1 and k, and consecutive elements either increase or have no common factors, modulo 1,000,000,007. The number of qualifying arrays is to be computed based on the constraints and examples provided.

Uploaded by

Musa Mohammad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
104 views3 pages

Coding Exercise 1

The function dfcount takes integers n and k as parameters. It returns the number of arrays of length n where each element is between 1 and k, and consecutive elements either increase or have no common factors, modulo 1,000,000,007. The number of qualifying arrays is to be computed based on the constraints and examples provided.

Uploaded by

Musa Mohammad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Coding Exercise

You must correctly implement the function described in the prompt below.

Feel free to test out pieces of code to help you write the solution.

Please thoroughly test that the final code implements the function correctly.

Prompt
Function signature: dfcount(n: int, k: int) -> int

Hero likes some arrays. The arrays he likes are the arrays that
have all of the following properties:

The length of the array is n.

Each element is an integer between 1 and k, inclusive.

Whenever A and B are two consecutive elements of the array (in


this order), we have (A <= B) or (A mod B != 0).

For example, suppose n=4 and k=7.

Hero will like the array {1,7,7,2} because it has the right
length, all elements are in the correct range, 1 <= 7, 7 <= 7,
and 7 mod 2 != 0.

Hero will not like the array {4,4,4,2}.

You are given the ints n and k.

Let X be the number of different arrays Hero likes.

Compute and return the value (X mod 1,000,000,007).

Constraints

-n will be between 1 and 50,000, inclusive.

-k will be between 1 and 50,000, inclusive.

Examples

0)

2
2

Returns: 3

The three arrays Hero likes are {1,1}, {1,2}, and {2,2}.

1)

Returns: 4

The four arrays Hero likes in this case are {1,1,1}, {1,1,2},
{1,2,2}, and {2,2,2}.

2)

Returns: 15

3)

107

Returns: 107

4)

Returns: 2292
5)

42

23

Returns: 301026516

You might also like