# [Solution] Distinct Dilemma solution codechef

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.

## [Solution] Distinct Dilemma solution codechef

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

### Input Format

• 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.

## [Solution] 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


### Sample Output 1

3
3


## Distinct Dilemma solution Explanation

• 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.