Number Of Sequence

Hard
0/120
Average time to solve is 50m
profile
Contributed by
9 upvotes
Asked in companies
OlaCodenationZoho Corporation

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].
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
3
0 -1 -1
3
0 1 -1

Sample Output 1 :

6
3

Explanation of the Sample Input 1:

In the first test case, The following sequences are possible: [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 0, 1], [0, 0, 2]. Hence the answer is 6.

In the second test case, The following sequences are possible: [0,1,0],[0,1,1], and [0,1,2]. Therefore the final answer is 3.

Sample Input 2 :

2
3
0 1 2
3
-1 -1 2

Sample Output 2 :

1
2
Hint

Can we use the Chinese remainder theorem?

Approaches (1)
Chinese Remainder Theorm

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.
Time Complexity

O(N*log(log(N))), where ‘N’ is the number given.
 

Since we are finding all the prime numbers from 0 to ‘N’, the overall time complexity is O(N*log(log(N))).

Space Complexity

O(N), where ‘N’ is the number given.

 

Since we are using an array to store prime numbers, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Number Of Sequence
Full screen
Console