fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3.  
  4. // Function to find a pair in an array with given sum using Hashing
  5. void findPair(int arr[], int n, int sum)
  6. {
  7. 	// create an empty map
  8. 	std::unordered_map<int, int> map;
  9.  
  10. 	// do for each element
  11. 	for (int i = 0; i < n; i++)
  12. 	{
  13. 		// check if pair (arr[i], sum-arr[i]) exists
  14.  
  15. 		// if difference is seen before, print the pair
  16. 		if (map.find(sum - arr[i]) != map.end())
  17. 		{
  18. 			std::cout << "Pair found at index " << map[sum - arr[i]] << 
  19. 						 " and " << i;
  20. 			return;
  21. 		}
  22.  
  23. 		// store index of current element in the map
  24. 		map[arr[i]] = i;
  25. 	}
  26.  
  27. 	// we reach here if pair is not found
  28. 	std::cout << "Pair not found";
  29. }
  30.  
  31. // Find pair with given sum in the array
  32. int main()
  33. {
  34. 	int arr[] = { 1, 1, 2, 2, 1, 2, 2};
  35. 	int sum = 2;
  36.  
  37. 	int n = sizeof(arr)/sizeof(arr[0]);
  38.  
  39. 	findPair(arr, n, sum);
  40.  
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pair found at index 0 and 1
https://ideone.com/LD8DOs
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!