URI (BEECROWD) - 2290 - Números Apaixornados - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 2290

Enunciado:

Será dado a você um vetor com N números, onde todos estarão em pares. Porém somente dois desses números acabaram ficando sem par, esses números são ditos números apaixornados, você consegue identificar quais são esses números?

Por exemplo, A = {1, 1, 3, 3, 5, 5, 5, 7}, os números apaixornados são 5 e 7.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>

void merge(long long int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    long long int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(long long int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
int main() {
    long long int resposta[2], numeros[100001], atual, proximo;
    int n, contador, indice;
    
    while (scanf("%i", &n) != EOF) {
        
        memset(numeros, 0, sizeof(numeros));
            
        for (indice = 0; indice < n; indice++)
            scanf("%lld", &numeros[indice]);
        
        mergeSort(numeros, 0, n-1);
        
        contador = 0;
		for (indice = 0; indice < n && contador < 2; indice++) {
		    
		    atual = numeros[indice];
		    proximo = numeros[indice + 1];

			if (atual == proximo && indice < n - 1)
				indice++;
			else if (contador++ == 1)
			    printf("%lld\n", atual);
			else
			    printf("%lld ", atual);
		}
    }
    return 0;
}

Código em C++:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int compara (const void *a, const void *b) {
    
    long long int *a2 = (long long *)a;
    long long int *b2 = (long long *)b;

	if (*a2 == *b2)
		return 0;
	else if (*a2 > *b2)
		return 1;
	else
		return -1;

}

int main() {
    long long int resposta[2], numeros[100001];
    int n, contador, indice;
    
    while (scanf("%i", &n) != EOF) {
        
        memset(numeros, 0, sizeof(numeros));
            
        for (indice = 0; indice < n; indice++)
            scanf("%lld", &numeros[indice]);
        
        qsort(numeros, n, sizeof(long long int), compara);
        
        contador = 0;
		for (indice = 0; indice < n && contador < 2;) {

			if (numeros[indice] == numeros[indice + 1] && indice < n - 1)
				indice += 2;
				
			else {
				cout << numeros[indice++];
				
				if (contador++ == 1)
					cout << endl;
					
				else
					cout << " ";
			}
		}
    }
    return 0;
}