Esercizio pratico #5

Lezione 14 di 14 del corso Lista doppiamente concatenata - Serie sulle strutture dati n. 6 di Coddy.

Sfida

Facile

Dato un array di interi ordinato arr (i valori di una lista doppiamente collegata ordinata) e un intero target, scrivi una funzione countPairs che restituisca il numero di coppie di indici (i, j) tali che i < j e arr[i] + arr[j] == target.

Supponi che l’input non contenga valori duplicati.

Usa una lista doppiamente collegata per risolvere questo problema! Usa due puntatori da entrambe le estremità, spostandoli verso l’interno.

Devi usare la classe DoublyLinkedList (fornita in doublylinkedlist.<ext> insieme a node.<ext>) — non usare funzionalità integrate del linguaggio come reverse degli array, slicing, sort o operazioni sulle liste della libreria standard per calcolare il risultato.

Provalo tu

#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;
}