[Coding] Distinct Dilemma solution codechef

[Coding] Distinct Dilemma solution codechef

 

You are given an array AA of NN integers. You can do the following two types of operations any (possibly zero) number of times:

  • Pick two indices ii and jj (1i,j|A|,ij)(1≤i,j≤|A|,i≠j). Change Aj:=Aj+AiAj:=Aj+Ai and remove the ithith element from the array.
  • Pick an index ii (1i|A|)(1≤i≤|A|). Split AiAi into two positive integers XX and YY such that X+Y=AiX+Y=Ai. Remove the ithith element from the array and append elements XX and YY to the array.

Find the maximum number of distinct elements present in the array after performing any number of operations of the above two types.

[Coding] Distinct Dilemma solution codechef

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains an integer NN – the size of the array.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, output the maximum number of distinct elements present in the array after performing any number of operations of the above two types.

[Coding] Distinct Dilemma solution codechef

  • 1T1001≤T≤100
  • 2N10002≤N≤1000
  • 1Ai1051≤Ai≤105

Sample Input 1 

2
3
1 2 4
4
1 1 3 4
[Coding] Distinct Dilemma solution codechef  
3
3

[Coding] Distinct Dilemma solution codechef

  • Test case 11: The maximum number of distinct elements that can be achieved by performing some finite number of operations on the given array is 33. Some examples of the final array are:

    • [1,2,4][1,2,4] : Perform no operation on the given array.
    • [1,2,1,3][1,2,1,3] : Perform operation 22. Choose i=3i=3. Here, A3=4A3=4. Break it as X=1X=1 and Y=3Y=3. On removing A3A3 and appending XX and YY, we get [1,2,1,3][1,2,1,3]. This array has 33 distinct elements.
  • Test case 22: The maximum number of distinct elements that can be achieved by performing some finite number of operations on the given array is 33. Some examples of the final array are:

    • [1,1,3,4][1,1,3,4] : Perform no operation on the given array.
    • [1,1,3,2,2][1,1,3,2,2] : Perform operation 22. Choose i=4i=4. Here, A4=4A4=4. Break it as X=2X=2 and Y=2Y=2. On removing A4A4 and appending XX and YY, we get [1,1,3,2,2][1,1,3,2,2]. This array has 33 distinct elements.
    • [2,3,4][2,3,4] : Perform operation 11. Choose i=1i=1 and j=2j=2. On changing A2:=A1+A2=1+1=2A2:=A1+A2=1+1=2 and removing A1A1, we get [2,3,4][2,3,4]. This array has 33 distinct elements.
    • ANSWER

      Click Here

Leave a Comment