fork download
  1. // http://w...content-available-to-author-only...t.com/find-pair-with-given-sum-array/
  2. // To compile and run: gcc 0001.c `pkg-config --cflags --libs glib-2.0` && ./a.out
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. #include <glib.h>
  8.  
  9. int cmp(const void * a, const void * b) {
  10. return (*(int *)a - *(int *)b);
  11. }
  12.  
  13. // 2. O(nlogn) - time complexity; O(1) - space complexity
  14. void findPairBySorting(int arr[], int n, int sum) {
  15. int low = 0, high = n - 1, temp_sum;
  16. qsort(arr, n, sizeof(int), cmp);
  17. while (low < high) {
  18. temp_sum = arr[low] + arr[high];
  19. if (temp_sum == sum) {
  20. printf("Pair found: %i and %i.\n", arr[low], arr[high]);
  21. return;
  22. }
  23. temp_sum < sum ? low++ : high--;
  24. }
  25. printf("Pair not found.\n");
  26. }
  27.  
  28. // 3. O(n) - time complexity; O(n) - space complexity
  29. void findPairByHashing(int arr[], int n, int sum) {
  30. int second_number;
  31. GHashTable * hash = g_hash_table_new(g_int_hash, g_int_equal);
  32. for (int i = 0; i < n; i++) {
  33. second_number = sum - arr[i];
  34. if (g_hash_table_lookup(hash, &second_number) != NULL) {
  35. printf("Pair found: %i and %i.\n", second_number, arr[i]);
  36. return;
  37. }
  38. g_hash_table_insert(hash, &arr[i], &i);
  39. }
  40. printf("Pair not found.\n");
  41. }
  42.  
  43. int main() {
  44. int arr[] = { 8, 7, 2, 5, 3, 1};
  45. // Outputs: Pair found: 2 and 8.
  46. findPairBySorting(arr, sizeof(arr) / sizeof(int), 10);
  47. // Outputs: Pair found: 3 and 7.
  48. findPairByHashing(arr, sizeof(arr) / sizeof(int), 10);
  49. return 0;
  50. }
  51.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.c:7:18: fatal error: glib.h: No such file or directory
 #include <glib.h>
                  ^
compilation terminated.
stdout
Standard output is empty