Find X Value of Array I

You are given an array of positive integers nums, and a positive integer k.

You are allowed to perform an operation once on nums, where in each operation you can remove any non-overlapping prefix and suffix from nums such that nums remains non-empty.

You need to find the x-value of nums, which is the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x when divided by k.

Return an array result of size k where result[x] is the x-value of nums for 0 <= x <= k - 1.

A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.

A suffix of an array is a subarray that starts at any point within the array and extends to the end of the array.

Note that the prefix and suffix to be chosen for the operation can be empty.

Example 1
Inputnums = [1,2,3,4,5], k = 3
Output[9,2,4]
There are 9 ways to leave a subarray with product remainder 0 modulo 3, 2 ways with remainder 1, and 4 ways with remainder 2.
Example 2
Inputnums = [1,2,4,8,16,32], k = 4
Output[18,1,2,0]
Among all possible remaining non-empty subarrays, the counts of product remainders modulo 4 are 18 for 0, 1 for 1, 2 for 2, and 0 for 3.

Constraints

  • 1 <= nums[i] <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= k <= 5

Asked at 1 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate