AnswerΒΆ
Given the array defined in question.h:
1 2 3 4 5 | const size_t nint = 100;
int intarr[nint] = {591, 146, 886, 335, 554, 331, 702, 828, 128, 64,
497, 797, 831, 775, 23, 581, 870, 182, 526, 181, 918, 6, 811, 349, 913,
817, 995, 583, 993, 992, 999, 343, 779, 614, 380, 2, 260, 577, 487, 129,
268, 106, 869, 120, 271, 57, 783, 471, 477, 647};
|
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <stdlib.h>
#include <stdio.h>
#include "question.h"
int comp (const void *val1, const void *val2) {
int v1 = *((int*)val1);
int v2 = *((int*)val2);
if (v1 > v2) return 1;
if (v1 < v2) return -1;
return 0;
};
int main() {
int given = 518;
// step 1: sort the array.
qsort((void *)intarr, nint, sizeof(int), comp);
// step 2: search the sorted array with only two loops.
for (size_t ix = 2; ix < nint; ix++) {
for (size_t iy = 0, iz = ix-1; iy < iz;) {
int sum = intarr[ix] + intarr[iy] + intarr[iz];
if (sum < given) {
iy++;
} else if (sum > given) {
iz--;
} else {
printf("%d + %d + %d = %d\n",
intarr[iy], intarr[iz], intarr[ix], given);
return -1;
};
};
};
return -1;
};
|