Last Updated: 18 Jun, 2021

Number Of Sequence

Hard

Asked in companies

Solve now

Problem statement

A sequence is called nice by a coding ninja if the following conditions are met:

0 <= ‘ARR’[k] <= k 
‘ARR’[k] = ‘ARR’[m] mod k, for all pairs of k,m such that k divides m.

You are given a sequence of integers ‘ARR’ where some numbers may be -1. Find and print the number of nice sequences you can create by changing each -1 to a non-negative integer. As this number can be quite large, your answer must be modulo it by 10 ^ 9 + 7.

For example:

Given ‘N’ = 3, 
'A' = {0, -1, -1} 
Then the answer is 6 because following sequences are possible:[0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 0, 1], [0, 0, 2].

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output Format :

For each test case, You are supposed to return the total number of nice arrays that can be formed.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 3000
0 <= 'ARR[i]’ <= 10 ^ 6

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

The idea is that by using the Chinese Remainder Theorem, we can uniquely find ‘ARR[k]’ for a nice reconstructed sequence. The Chinese remainder theorem states that if one knows the remainder of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

We know that if we have a nice sequence we can find a set ‘S’, as each nice sequence corresponds to some set ‘S’. Conversely, let correspond to ‘ARR’. Then, for each prime and for each ‘K’, we can find a maximal ‘B’ such that ‘K’ is divisible by ‘P’ ^ ‘B’, where ‘P’ denotes a prime number.

That implies

‘ARR[k]’ is equivalent to ‘ARR[P ^ B], which in turn is congruent to ‘ARR[‘P’ ^ ‘A’] mod ‘P ^ B’.

Where ‘P’ ^ ‘A’ denotes the highest value which is less than ‘ARR[k]’.

The steps are as follows:

Convert the given vector ‘ARR’ into an array ‘V’ which now has 1-based indexing.
Maintain an array ‘primes’ which store all the prime numbers from 0 to ‘N’.
Traverse from 2 to square-root of ‘N’, and if the ‘i’th number is not prime, then continue, else, from ‘i’th number to ‘N’, make jumps of ‘i’ size and mark all the jumps as not prime. This is known as the prime sieve technique.
Maintain a ‘res’ that stores the final result.
Initialize ‘res’ to 1.
Loop through ‘primes’ and for each ‘prime[i]’, and check if the answer is non-zero or not.
If the answer is non-zero, ‘res’ = ‘res’ * ‘primes[i]’.
Modulo ‘res’ by 10 ^ 9 + 7.
Return ‘res’ as the final result.

Solve now