distinct dilemma

This problem was fairly simple compared to the Rating that it had, I think this was part of the Starters 81 Contest, maybe, the overall logic and the core of the Problem was understanding what we are doing with the operations that are mentioned in the Problem Statement, the 2 operations if understood and imagined well, they just tell us that we can make any element equal to any other element and for this case as we require "Distinct" Elements so we should start in the manner of a Natural Numbers Series, like 1,2,3,4... so, overall what we are doing is that we are just starting to make these Natural Numbers, or we can say the Distinct Numbers and we will be doing this as long as we have the capability, which means we have enough quantity of numbers to do this thing.

For example, if we have input array  as : 1,2,4. 

So, I know that the summation of the array is 7, and will start by making 1, so that's <=7 then 2, now the summation is 3, still <=7, now, 3, summation became 6 which is <=7, but when I try going for 4, the summation becomes 10 which is not <=7, so we just say that we can make at most 3 distinct elements in the resultant array. That's it. 

Why Do C Programmers use C...? If you know, you know

Problem Statement:-

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

• Pick two indices $�$ and $�$ $(1\le �,�\le \mathrm{\mid }�\mathrm{\mid },�\mathrm{\ne }�)$. Change ${�}_{�}:={�}_{�}+{�}_{�}$ and remove the ${�}^{�ℎ}$ element from the array.
• Pick an index $�$ $(1\le �\le \mathrm{\mid }�\mathrm{\mid })$. Split ${�}_{�}$ into two positive integers $�$ and $�$ such that $�+�={�}_{�}$. Remove the ${�}^{�ℎ}$ element from the array and append elements $�$ and $�$ 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.

Input Format

• The first line contains an integer $�$ denoting the number of test cases. The $�$ test cases then follow.
• The first line of each test case contains an integer $�$ - the size of the array.
• The second line of each test case contains $�$ space-separated integers ${�}_1,{�}_2,\dots ,{�}_{�}$.

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.

Constraints

• $1\le �\le 100$
• $2\le �\le 1000$
• $1\le {�}_{�}\le 10^5$

Sample 1:

Input

Output

2
3
1 2 4
4
1 1 3 4

3
3

Explanation:

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

  • $[1,2,4]$ : Perform no operation on the given array.
  • $[1,2,1,3]$ : Perform operation $2$. Choose $�=3$. Here, ${�}_3=4$. Break it as $�=1$ and $�=3$. On removing ${�}_3$ and appending $�$ and $�$, we get $[1,2,1,3]$. This array has $3$ distinct elements.

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

  • $[1,1,3,4]$ : Perform no operation on the given array.
  • $[1,1,3,2,2]$ : Perform operation $2$. Choose $�=4$. Here, ${�}_4=4$. Break it as $�=2$ and $�=2$. On removing ${�}_4$ and appending $�$ and $�$, we get $[1,1,3,2,2]$. This array has $3$ distinct elements.
  • $[2,3,4]$ : Perform operation $1$. Choose $�=1$ and $�=2$. On changing ${�}_2:={�}_1+{�}_2=1+1=2$ and removing ${�}_1$, we get $[2,3,4]$. This array has $3$ distinct elements.

Code Implementation:-

'''

Time Usage:-

Without count usage(while loop): 0.05 secs

With count usage(while loop): 0.05 secs

With for loop usage: 0.05 secs

'''

'''

THIS SAME LOGIC IN  C++17 TAKES 0.01 secs.

PS!!

'''

for _ in range(int(input())):

    n=int(input())

    nums=list(map(int,input().split()))

    s=sum(nums)

    # count and var1 are required when we are using while loop

    # count=0

    # var1=1

   

    sum1=0

    '''

    with for loop we don't have to use var1 and count variables, and also 'for' loop in

    Python runs in C compiler so its comparatively faster than the 'while' loop in Pytho

    , in this case the difference is not that clear bcz the limits are less, if we

    compare them for large iterations then we will be able to see the difference easily

    '''

    for i in range(1,9999999999):

        sum1+=i

        if(sum1>s):

            print(i-1)

            break

    '''

    Can also use while loop but it's always advised to use for loop in Python, so I

    used it

    '''

   

    # while(True):

    #     sum1+=var1

    #     var1+=1

    #     if(sum1>s):

    #         break

    #     count+=1

   

    # We can use either of the two lines given below with the while loop

    # print(count)

    # print(var1-2)

C++ Implementation:-

#include <bits/stdc++.h>

#define fast ios_base::sync_with_stdio(false);

using namespace std;

int main() {

    fast

    // cout<<"Hola Todo El Mundo!\n";

    int t;

    cin>>t;

    while(t){

        int n;

        cin>>n;

        int nums_sum=0;

        vector<int> nums(n);

        for(int i=0;i<n;i++){

            cin>>nums[i];

            nums_sum+=nums[i];

        }

        int ans_sum=0;

        for(int i=1;i<=9999999;i++){

            ans_sum+=i;

            if(ans_sum>nums_sum){

                cout<<i-1<<endl;

                break;

            }

        }

       

        t--;

    }

    return 0;

}

Explanation:-

The only logic is that by both the operations we can make change any number to any other number, like we can just start making a Series of Natural Numbers, but this will continue up till the summation of that series is <= the summation of the input list, when this condition fails, we just print the number of distinct elements that were in the resultant array.