fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> Pair;
  5.  
  6. // Function to check if Quad-tuple exists in an array with given sum
  7. void quadTuple(int arr[], int n, int sum)
  8. {
  9.     // create an empty map
  10.     // key -> sum of a pair of elements in the array
  11.     // value -> vector storing index of every pair having that sum
  12. 	unordered_map<int, vector<Pair>> map;
  13.  
  14.     // consider each element except last element
  15. 	for (int i = 0; i < n - 1; i++)
  16. 	{
  17. 	    // start from i'th element till last element
  18. 		for (int j = i + 1; j < n; j++)
  19. 		{
  20.             // calculate remaining sum
  21. 			int val = sum - (arr[i] + arr[j]);
  22.  
  23. 		    // if remaining sum is found in the map, we have found a Quad-tuple
  24. 			if (map.find(val) != map.end())
  25. 			{
  26. 				// check every pair having sum equal to remaining sum
  27. 				for (auto pair : map.find(val)->second)
  28. 				{
  29. 					int x = pair.first;
  30. 					int y = pair.second;
  31.  
  32. 					// if Quad-tuple don't overlap, print it and return true
  33. 					if ((x != i && x != j) && (y != i && y != j))
  34. 					{
  35. 						cout << "Quad-Tuple Found (" << arr[i] << " " << arr[j] 
  36. 							<< " " << arr[x] << " " << arr[y] << ")\n";
  37. 					}
  38. 				}
  39. 			}
  40.  
  41. 			// insert current pair into the map
  42.             map[arr[i] + arr[j]].push_back({i, j});
  43. 		}
  44. 	}
  45. }
  46.  
  47. // main function
  48. int main()
  49. {
  50. 	int arr[] = { 2, 7, 4, 0, 9, 5, 1, 3 };
  51. 	int sum = 20;
  52.  
  53. 	int n = sizeof(arr) / sizeof(arr[0]);
  54.  
  55. 	quadTuple(arr, n, sum);
  56.  
  57. 	return 0;
  58. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Quad-Tuple Found (4 0 7 9)
Quad-Tuple Found (4 9 2 5)
Quad-Tuple Found (4 9 7 0)
Quad-Tuple Found (4 5 2 9)
Quad-Tuple Found (0 9 7 4)
Quad-Tuple Found (9 5 2 4)
Quad-Tuple Found (9 1 7 3)
Quad-Tuple Found (9 3 7 1)
Quad-Tuple Found (1 3 7 9)
https://ideone.com/fwzL2O
language:
C++14 (gcc 8.3)
created:
7 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!