fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/1PHYH3
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!