How should I practice To Good Arrays?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is To Good Arrays associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

To Good Arrays

Learn this problem

● Hard

MicrosoftOA

See Microsoft hiring insights

Problem statement

You are given three integers N, M and K.

An array is said to be good if there is exactly K indices i such that A[i] * A[i + 1] is equal to M.

Find the number of good arrays A. Since the answer can be very large, return it modulo 10^9 + 7.

Input Format

The first line contains an integer, N, denoting one of the given three integers.

The next line contains an integer, M, denoting one of the three given integers.

The next line contains an integer, K, denoting one of the three given integers.

Function

countGoodArrays(N: int, M: int, K: int) → int

Examples

Example 1

N = 2M = 3K = 0return = 7

Given N = 2, M = 3, K = 0.

There exists 7 possible arrays A. Some of them are [3, 3] and [1, 2].

Example 2

N = 2M = 3K = 1return = 2

Given N = 2, M = 3, K = 1.

There exists only two possible arrays A which are [1, 3] and [3, 1].

Example 3

N = 5M = 10K = 2return = 1368

Given N = 5, M = 10, K = 2.

There exists a total of 1368 possible arrays A.

Constraints

2 <= N <= 10^9
3 <= M <= 10^9
0 <= K <= min(50, N - 1)