Deletion and Difference
Source: codechef
Difficulty: 1343

Deletion and Difference
You're given an array$A$of length$N$. You can perform the following operation on it:
Choose two indices$i$and$j$($1 \leq i \lt j \leq |A|$) such that$A_i = A_j$.
Delete both$A_i$and$A_j$from$A$, and append$|A_i - A_j|$to$A$.
The length of the array reduces by$1$, and all remaining elements are re-indexed to start from$1$.
Find the
minimum
possible length of$A$after performing this operation several (possibly, zero) times.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains a single integer$N$, denoting the length of$A$.
The second line contains$N$space-separated integers$A_1, A_2, \ldots, A_N$— the elements of$A$.
Output Format
For each test case, output on a new line a single integer: the minimum possible length of$A$after performing the given operation several times.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 2\cdot 10^5$$0 \leq A_i \leq N$The sum of$N$over all test cases won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test Case 1
: There are no deletions we can do. Hence, the answer is$4$, the size of the initial array.
Test Case 2
: We can choose$i = 1, j = 2$. Note that$A_1 = A_2 = 1$, and then insert their difference$0$back into the array while deleting the$1$s. Thus, the final array becomes$[0]$of size$1$.

Sample Input:
3
4
3 1 4 2
2
1 1
3
1 1 0

Sample Output:
4
1
1

C++ solution:
#pragma optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

ll n, x, i, ans;
bool check;

void solve()
{
    cin >> n;
    vector <ll> v(n + 1, 0); 
    for (i = 0; i < n; i++)
    {
        cin >> x;
        v[x]++;
    }
    check = false;
    for (i = 1; i <= n; i++)
    {
        if (v[i] > 1)
        {
            v[i] &= 1;
            check = true;
        }
    }
    ans = 0;
    if (v[0] || check)
    {
        ans++;
    }
    for (i = 1; i <= n; i++)
    {
        ans += v[i];
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    
    // Read the number of test cases
    tStr, _ := reader.ReadString('\n')
    t, _ := strconv.Atoi(strings.TrimSpace(tStr))

    for t > 0 {
        t--
        
        // Read the size of the array
        nStr, _ := reader.ReadString('\n')
        n, _ := strconv.Atoi(strings.TrimSpace(nStr))

        // Read the array elements
        arrStr, _ := reader.ReadString('\n')
        arrSlice := strings.Fields(arrStr)
        arr := make([]int, n)

        maxVal := 0
        for i := 0; i < n; i++ {
            arr[i], _ = strconv.Atoi(arrSlice[i])
            if arr[i] > maxVal {
                maxVal = arr[i]
            }
        }

        // Frequency array
        freq := make([]int, maxVal+1)
        for i := 0; i < n; i++ {
            freq[arr[i]]++
        }

        nonZeroOdd := 0
        totalZeroPairs := 0
        zerosFromInput := freq[0]

        for v := 1; v <= maxVal; v++ {
            if freq[v]%2 == 1 {
                nonZeroOdd++
            }
            totalZeroPairs += freq[v] / 2
        }

        totalZeros := zerosFromInput + totalZeroPairs
        finalZeros := 0
        if totalZeros > 0 {
            finalZeros = 1
        }

        ans := nonZeroOdd + finalZeros
        fmt.Println(ans)
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
            int N=sc.nextInt();
            int freq[]=new int[N+1];boolean count=false;
            for(int i=0;i<N;i++)
            {
                int m=sc.nextInt();
                freq[m]++;
                if(freq[m]>1){count=true;}
            }
            for(int i=0;i<=N;i++)
            {
                freq[i]=freq[i]%2;
            }
            int ans=0;
            for(int c:freq)
            ans+=c;
            if(count && freq[0]==0)
            ans+=1;
            System.out.println(ans);
        }

    }
}

JavaScript solution:
// your code goes here
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inLines = [];
rl.on("line", (line) => {
    inLines.push(line);
}).on("close", () => {
    processTestCases(inLines);
    process.exit(0);
});

function processTestCases(inLines) {
    let t = parseInt(inLines[0]); 
    let ind= 1;
    let res = [];

    while (t--) {
        let n = parseInt(inLines[ind]); 
        let arr = inLines[ind + 1].split(" ").map(Number); 
        ind += 2;

        let zero = arr.includes(0) ? 1 : 0; 

        let freqMap = new Map();
        arr.forEach(num => {
            if (num !== 0) freqMap.set(num, (freqMap.get(num) || 0) + 1);
        });

        let c = 0, z = 0;
        for (let [key, count] of freqMap) {
            if (count === 1) {
                c++;
            } else if (count % 2 === 0) {
                z++;
            } else { 
                c++;
                z++;
            }
        }

        res.push((zero === 1 || z >= 1) ? c + 1 : c);
    }

    console.log(res.join("\n"));
}

Python solution:
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    freq = [0]*(n+1)
    for x in a: freq[x] += 1
    for x in reversed(range(n+1)):
        while freq[x] >= 2:
            freq[x] -= 2
            freq[0] += 1
    print(sum(freq))

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  results = []
  test_cases.times do
    n = input[ptr].to_i
    ptr += 1
    a = input[ptr, n].map(&:to_i)
    ptr += n
    freq = Array.new(n + 1, 0)
    a.each { |x| freq[x] += 1 }
    (n.downto(0)).each do |x|
      while freq[x] >= 2
        freq[x] -= 2
        freq[0] += 1
      end
    end
    results << freq.sum
  end
  puts results.join("\n")
end

solve