Maximum Number Of Distinct Elements Solution codechef

Maximum Number Of Distinct Elements Solution codechef

Given an array B of length N, find an array A of length N where 0Ai109 such that array C where Ci=AimodBii{1,N} has maximum number of distinct integers.

In case of multiple answers, print any.

Input Format Maximum Number Of Distinct Elements Solution codechef

  • First-line will contain T, the number of test cases. Then the test cases follow.
  • Each test case contains two lines of input.
  • First-line contains a single integer N.
  • Second-line contains N space-separated integers B1,B2,,BN.

Output Format Maximum Number Of Distinct Elements Solution codechef

For each test case, output in a single line N space-separated integers A1,A2,,AN, the elements of the array A such that array C has the maximum number of distinct elements.

If the output array doesn’t follow the constraints or the number of distinct elements in the array C is less than the optimal value, you will receive a wrong answer verdict.

Constraints Maximum Number Of Distinct Elements Solution codechef

  • 1T105
  • 1N2105
  • 1BiN
  • 0Ai109
  • Sum of N over all tests is atmost 106.

Sample Input 1 Maximum Number Of Distinct Elements Solution codechef

3
3
2 1 3
2
1 1
6
1 2 3 3 2 1

Sample Output 1 Maximum Number Of Distinct Elements Solution codechef

3 1 2
2 3
0 1 2 3 4 5

Explanation Maximum Number Of Distinct Elements Solution codechef

Test Case 1: Array C={3mod2,1mod1,2mod3}={1,0,2}. So the number of unique elements are 3.

Test Case 2: Array C={2mod1,3mod1}={0,0}. So the number of unique elements is 1.

Test Case 3: Array C ={0mod1,1mod2,2mod3,3mod3,4mod2,5mod1} ={0,1,2,0,0,0}. So the number of unique elements are 3.

In all the 3 cases, the number of unique elements can’t be increased any further for any choice of the array A.

Leave a Reply

Your email address will not be published. Required fields are marked *

*