Practice #5
Lección 14 de 14 del curso Lista Doblemente Enlazada - Serie de Estructuras de Datos #6 de Coddy.
Desafío
FácilDado un arreglo de enteros ordenado arr (los valores de una lista doblemente enlazada ordenada) y un entero target, escribe una función countPairs que devuelva el número de pares de índices (i, j) con i < j y arr[i] + arr[j] == target.
Asume que la entrada no contiene valores duplicados.
¡Utiliza una lista doblemente enlazada para resolver este problema! Dos punteros desde ambos extremos, moviéndose hacia adentro.
Debes usar la clase DoublyLinkedList (proporcionada en doublylinkedlist.<ext> junto con node.<ext>) — no utilices funciones integradas del lenguaje como reverse de arreglos, slicing, sort u operaciones de listas de la biblioteca estándar para calcular el resultado.
Pruébalo tú mismo
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line1[8192];
char line2[64];
if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
int arr[4096];
int len = 0;
char* tok = strtok(line1, " \t\r\n");
while (tok) { arr[len++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int n = atoi(line2);
int r = countPairs(arr, len, n);
printf("%d\n", r);
return 0;
}
